Explore one of the biggest unsolved problems in theoretical computer science - the P vs NP problem - in this lecture by Professor Kevin Buzzard. Delve into the intriguing world of computational complexity, examining what computers can and cannot do quickly. Learn about the implications of this problem for security, cryptography, and artificial intelligence. Discover historical context from ancient Greek mathematics to modern computer science pioneers like Ada Lovelace and Alan Turing. Investigate practical applications, including public key cryptography and factoring large numbers. Gain insights into the nature of polynomial time algorithms and NP-complete problems. Consider the potential consequences if someone were to prove that P equals NP, and understand why this problem remains a central challenge in computer science and mathematics.
Overview
Syllabus
Introduction
Can Computers Control Killer Robots
What a Company Needs
Google Employees
Does Google have an army of killer robots
How many killer robots have Google actually got
Can computers think
Deepblue thinking
Problems
Ancient Greeks
Euclids Theorem
Trisection Angle
Conclusion
Ada Lovelace
A Theorem
Alan Turing
Computer programs
Conclusions
Practical Problems
Summary
Two Computer Programs
Polynomial Time
Public Key Cryptography
Complicated Knots
Multiply
Scale
Factoring
P and NP
NP Examples
Does P Equal NP
What would happen if someone proved P
Taught by
The Royal Institution
