P vs. NP: The Biggest Puzzle in Computer Science

Are there limits to what computers can do? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called Computational Complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science.

This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions.

00:00 Introduction to the P vs NP problem
02:16 Intro to Computational Complexity
02:30 How do computers solve problems?
03:02 Alan Turing and Turing Machines
04:05 George Boole and Boolean Algebra
05:21 Claude Shannon and the invention of transistors
06:22 John Von Neumann and the invention of the Universal Electronic Computer
07:05 Algorithms and their limits
08:22 Discovery of different classes of computational problems
08:56 Polynomial P problems explained
09:56 Exponential NP Problems explained
11:36 Implications if P = NP
12:48 Discovery of NP Complete problems
13:45 Knapsack Problem and Traveling Salesman problem
14:24 Boolean Satisfiability Problem (SAT) defined
15:32 Circuit Complexity Theory
16:55 Natural Proofs Barrier
17:36 Meta-complexity
18:12 Minimum Circuit Size Problem (MCSP)

[iamtheusualguy]

As a CS graduate student, the theoretical sections of the field are quite mind-bending and very profound in a way. I thnink often times people underestimate what deep insights questions in computer science can give back to the world. Thank you for showing such a nice summary of one of them!

[patrickgambill]

This video is good, but a few small details to add.
1. Solving P vs NP doesn't mean all encryption breaks overnight. RSA encryption could be broken if a polynomial algorithm is found for an np complete problem, but only if the polynomial isn't too big. Even polynomial algorithms can be unusable in practice. This is all assuming an explicit constructive proof P = NP is found. Non constructive proofs will not help solve any of the real world problems, and if it is shown P is not equal to NP, nothing will change. Even if an algorithm to break RSA is found, we can build other encryption methods using NP Hard problems like Travelling Salesman Problem (shortest path version).

2. The Travelling Salesman Problem (TSP) is NP hard in it's usual statement. It is only NP complete if you ask the question "is it possible to find a path that is shorter than a given length". If you ask the problem of finding the shortest path, this is not verifiable in polynomial time.

[sunkruhmhalaci]

Turing was brilliant and saved untold lives in WWII with his encryption work. How they treated him was horrible.

[manolismylonas]

So glad to see Shannon mentioned. He is massively underrated, he basically is the father of modern computers (let alone Communication and Information Theory)

[damareswaramaddepalli]

UG in CS and MS in CS now job less. Life is very hard. Watching the subject in this video brought me tears. The enthusiasm I shown in each and every class. Theory of computation, compiler construction and Micro processor integration. All three core subjects are simplified in this video. Thank you bringing my memory back. I will fight again to survive. 💔

[goGOgetITnow]

Im a teacher and I have to applaud your video style. It's excellent from an educational perspective with very sharp and clear visualisations and superb pace. Bravo.

[suzannecarter]

This was excellent! Scott Aaronson praised it highly for accuracy but did state that it would have been improved by addressing the difference between Turing machines and circuits (i.e., between uniform and non-uniform computation), and where the rough identities “polynomial = efficient” and “exponential = inefficient” hold or fail to hold.

[KeemDaDream]

What a well constructed video. I appreciate how it went from basic Computer Science knowledge and gradually introduced higher level Computer Science topics in a simply put way.

[chrism]

Ugh...listen. I'm glad you took the time to explain the P=NP problem...but your conclusion that if P=NP, then suddenly we have the polynomial algorithm for every NP problem is just silly. Knowing that P=NP just tells us that a solution exists. It would not make us any closer to finding it.

[Salted_Potato]

Its mind boggling how many consistently great videos Quanta Magazine puts out frequently. Thank you for this gift to the world.

[petergibson]

His last question "Will we be able to understand the solution?" is the most profound question of all.
It reminds me of the computer "Deep Thought" in "The Hitchiker's Guide to the Galaxy" which spent generations trying to solve the problem of "Life the Universe and Everything".
After many hundreds of years it came up with the
But what does THAT mean ????

[djdedan]

Clearest explanation I’ve seen. Maybe it could’ve been paced slightly slower at points but nothing a manual pause and rewind won’t fix.

[elliotn]

Plain Boolean formulas cannot operate like a Turing machine because they have a fixed bound on computation (once you assign values to the variables you can simplify the expression in a fixed amount of time). For a paradigm to be Turing complete it must be possible for it to run forever, which requires conditional loops. Boolean circuits can be made Turing complete by introducing registers (for memory) and a clock to synchronize computational steps, but they can no longer be represented as pure Boolean formulas.

[prayagbhatt]

One of the best explanations of P, NP. I recalled my Theory of Computation, Information Security lectures and found it really fascinating. The insights are really cool and best explained. Thank you so much !!!

[incomplete]

Its like the RSA encryption 'problem' where it took normal computers an exponential ammount of time to bruteforce RSA encryption, it took a polynomial ammount of time to bruteforce on a quantum computer.

[veroxid]

I've always been in the "NP is just P we haven't figured out yet" category. That's how *all* science *_has always_* been; just like how it turned out magic was just a symptom of our lack of understanding of physics, NP is just a side-effect of our lack of understanding of mathematics.

[SYK.]

As someone who has a degree is philosophy and now working on a cs degree, it’s fascinating to see all the overlap when it comes to thinking about these kinds of problems. Great video!

[Rarests]

I love how he says 'if humanity survives long enough'. Great reminder, we really need to do better.

[abraruralam]

it's fun looking into the CSAT problem and trying to figure out exactly why you can't just assume the output to be 1 and trace it back to a random possible input combination.

It eventually comes down to these two facts:

1. logic gate outputs can get shared between logic gate inputs.
E.g: say, the output of an OR gate is connected to 2 (or more) AND gate inputs.

2. Logic gates AND and OR have multiple inputs mapped to their outputs. This means, they are many-to-one functions and do not have inverse functions. As a result, when you try to trace back from a given output, you have to randomly guess an input every time. This wouldn't be a problem on its own but due to our first point (logic gate outputs can get shared between logic gate inputs), when two guessed inputs end up meeting at a common output, they won't necessarily match so you end up with 1 and 0 being output value simultaneously.

And that's where the computational complexity increases drastically, because now you have to keep an account of all those common outputs branching into multiple inputs, so that your guessed inputs align when they meet there.

[oldbrokenhands]

Thanks for this, when I took computer science classes at UTD, this was glossed over in a slide, and given maybe two sentences in the textbook.