YoVDO

What Computers Can't Do - With Kevin Buzzard

Offered By: The Royal Institution via YouTube

Tags

Theoretical Computer Science Courses Algorithmic Complexity Courses Public Key Cryptography Courses

Course Description

Overview

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.

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

Related Courses

Approximation Algorithms Part I
École normale supérieure via Coursera
Approximation Algorithms Part II
École normale supérieure via Coursera
Automata Theory
Stanford University via edX
Computation in Complex Systems
Santa Fe Institute via Complexity Explorer
Computing: Art, Magic, Science
ETH Zurich via edX