P vs. NP: The Biggest Puzzle in Computer Science

Read about about "Complexity Theory’s 50-Year Journey to the Limits of Knowledge" at Quanta Magazine: www.quantamagazine.org/complexity-theorys-50-year-…

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!

I might take a crack at this on a chalkboard while I'm working my janitor job at MIT

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.

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

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

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.

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.

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.

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 answer.....42. But what does THAT mean ????

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.

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

Did NOT expect a Boolean logic primer in a P versus NP video. 🎉

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 !!!

Im an electrical engineering graduate besides understanding in electricity what really shakes me is understanding of how computer thinks. I really love it as side hobby. 😊

Best video I’ve seen in a long time. Honestly. Great, on the point presentation of distinct very important, fundamental concepts of our time

I have discovered that some programs have parts of code of P class and parts of code of NP class. There are classes of relaxations that use heuristics that can solve some problems but with no warranty about its success or about its optimality.

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.

I briefly dabbled into this topic in a Computer arithmetic hardware implementation course that I took in grad school ( MS Microelectronics Engineering) . Mainly the part on circuit complexity ( as that was the applicable concept to the course). It’s was a really interesting topic/course, especially the part of the course where I got to optimise a hardware implementation of an FFT algorithm on an FPGA by applying the techniques in the course.

2:17 study of inherent resources, such as T & S needed to solve a computational problem woah woah, so precisely put definition. awesome.