What Computers Can't Do - With Kevin Buzzard

This course introduces the P vs NP problem in theoretical computer science: whether every problem whose solution is quickly verifiable can also be quickly solved. It uses examples including public-key cryptography, factoring, complicated knots, and polynomial-time algorithms.

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