P vs. NP and the Computational Complexity Zoo

P vs. NP and the Computational Complexity Zoo


Today I wanna talk about the deepest unanswered question in computer science, and, maybe in all of math. A problem called P vs. NP. And I wanna talk about how ideas from computing show up in the everyday world around us, and how problems as seemingly disparate as protein folding and making up crossword puzzles share a common core difficulty that turns out to be a lot like Sudoku, well, okay basically it is Sudoku. In 2000 the Clay institute offered 1 Million dollar each for the solutions to seven key problems in Math — The Millennium Prize problems. These are profound and difficult problems and for most of them it takes a lot of specialized knowledge to even understand the question. Of the seven problems P vs. NP was both the most recently conceived — in 1971, and by far the easiest one to understand and explain. And in March 2010 the Clay Institute awarded the first of its seven prizes for the solution to, yeah, not P vs. NP. So, what is the P vs. NP question? Well, back in the 1970s computer scientists were busily figuring out how to program their retro-fabulous, cabinet-sized computers to solve all the world’s problems. Sometimes the first program anyone could think of for a particular problem would be unworkably slow but then, over time people would come up with clever ways to make it faster, or at least, that happened for some problems. For others, nobody was coming up with faster programs. To get a handle on the situation they started sorting the problems into classes based on how fast the program can solve them. For problems like multiplication they had really fast programs, and for others, like playing absolutely perfect chess they figured out that there just was no fast program. But for a bunch in-between they weren’t sure whether there was a fast way to do it. So, they kept trying. This is where P and NP come in. Skipping a ton of details for a second, P is a class that basically includes all the problems that can be solved by a reasonably fast program, like multiplication or alphabetizing a list of names. And then, around and including P we sort of discovered a class called NP That’s all the problems where, if you’re given a correct solution you can at least check it in a reasonable amount of time. NP was totally maddening, because it contained lots of important problems like vehicle routing and scheduling and circuit design and databases. And often, we get lucky and find that an NP problem was actually a part of P and we’d have our fast program. But, for a lot of them that didn’t seem to be happening. So people started to wonder whether everything in NP would turn out to be in P or if there were some NP problems that were truly harder than the ones in P. That’s the P vs. NP question. If all the NP problems are really in P, a lot of important puzzles we’ve been struggling with are gonna turn out to be easy for computers to solve. Puzzles connected to biology, and curing cancer; Puzzles in business and economics. We’d have a lot of miracle answers almost overnight. And also the encryption we use for things like online banking would be easy to crack, because it’s based on NP problems. Okay, examples: I like to think of the problems in NP as being basically like “puzzles” because I think what makes a puzzle a puzzle is that it’s a problem where you can give away the answer, and that’s what NP means. Like with Sudoku. Sudoku puzzles can take a long time to solve but if I give you a solved Sudoku grid checking it for mistakes is pretty quick. Outside of NP there are problems where it’s hard to even check an answer. Like, what’s the best move to make in this chess game? I could tell you the answer but how would you know whether I’m right? Well, you wouldn’t, because finding out requires a calculation so enormous that there’s a pretty good argument we’ll never be able to build a computer that could do it. To me, that’s not a very good puzzle. It’s practically impossible to know whether you’ve solved it. On the other side, are all the reasonable, solvable puzzles in P. These are clearly also in NP because one way to check an answer is to go through the process of finding it yourself. Like, if I were to tell you that the answer to 51 x 3 is 153, how would you check whether I’m right? You’d probably just multiply 51 by 3 yourself because it’s fast to do it, but Sudoku is different, or at least, we think it is. It seems like solving a Sudoku grid is a lot harder than checking a solution, but in fact nobody’s been able to prove it yet. As far as we know, there could be a clever way of playing Sudoku, much much faster. So that’s the question: Does being able to quickly recognize correct answers mean there’s also a quick way to find them? Nobody knows for sure, but either way, figuring out exactly how this works would teach us something important about the nature of computation. It gets weirder from here but first: three important details. 1. You might be thinking: hey, Sudoku is tough and all but it’s not that hard. What’s the big deal? Well, we’re really talking about how the difficulty scales up as you make the problem bigger and bigger. Like, how much harder is a 100×100 Sudoku grid than a standard 9×9 grid? We’ve been making computers exponentially faster as time goes on, so, for problems that don’t get exponentially harder as they get bigger all we have to do is wait for computers to get more powerful and then, even huge versions of those problems will be easy to solve by a computer. Like, multiplication problems are pretty easy for computers, even with enormous numbers. As the numbers get bigger, multiplying them just doesn’t get harder very fast. These days, the phone is what would have been referred to in the 1970s as a “supercomputer”. And you’d have to make up truly huge multiplication problems to stand up to all the computational power we’ve got now. Lots of familiar puzzles like mazes and Rubik’s cubes are in the same camp. Hard for people, but easy work for computers. And then there’s Sudoku. Computers can usually solve a 9×9 grid in a few milliseconds even though humans find them challenging. But as you make the grid bigger the problem just gets really hard, rapidly getting out of reach for even the most powerful computers. 2. P stands for “Polynomial time”. In P the number of steps you have to do to solve a problem, and therefore the amount of time that it takes, is some polynomial function of its size. “Polynomial” is a mishmash of Greek and Latin meaning “many names”, which is, regrettably a pretty typical example of Math’s flair for unhelpful terminology. Anyway, polynomials are functions involving n or n² or n to other powers like these, but importantly they’re not exponential functions like 2ⁿ, which gets to be a ton of steps really fast as n goes up, a lot quicker than n². So that’s P, it’s problems like mazes and multiplication where the number of steps required isn’t that bad compared to the size of the problem. NP is all about polynomial time *checking*. NP stands for “Non deterministic polynomial time”, which, being math terminology is almost a mean spirited way of saying that if you had a bajillion computers then you could check all possible answers at the same time. You could find a correct solution in polynomial time. 2.5. We’re actually talking about the number of steps required to solve a problem in the worst case scenario. Like, how many steps does it take to unscramble a Rubik’s cube? Well, when it’s scrambled like this, it takes one step, but it can get a lot worse. Similarly, some 9×9 Sudokus are harder than others. People also look at things like the best case and the average case, but worst case analysis is what we know the most about. 3. Actually, pretty much everybody thinks it’s obvious that NP contains more problems than P, it’s just that we haven’t been able to prove it. The bad news for fast solutions came in the early 1970s where complexity researches realized that dozens of those NP problems they were struggling with were essentially all the same problem! (with some easy polynomial time complications thrown in here and there) These are call “NP-complete” problems, and since that first batch in the 70s we’ve added Sudoku and protein folding, and problems underlying puzzles and games like Battleship, FreeCell, Master Mind, Tetris, Minesweeper, and making up crossword puzzles. Even classic video games like Super Mario Bros. and Metroid turn out to be connected to NP complete-level traversal problems. NP-complete is yet another Math phrase meaning that these problems include all the really hard parts of every NP problem. A fast program for solving any NP-complete problem could be used to solve every problem in NP. The whole class would instantly collapse. So yeah, amazingly, Sudoku is hard because it involves, literally, the same NP-complete task that makes protein folding hard. If you come up with a profoundly faster way to play Sudoku let somebody know, okay? because fast protein folding would help us cure cancer. But the fact that a bunch of smart people have all been unsuccessful coming up with fast programs to solve what turned out to be, essentially, the same problem, looks like pretty good clue that the fast programs just aren’t out there. So why has it been so hard to prove P vs. NP on way or the other? Well, fun fact, proving things is an NP problem. The P vs. NP question itself *is* one of these problems. So yeah, this might be difficult, or not? we don’t know. As the field of computational complexity has developed, we’ve discovered a lot of complexity. The P vs. NP question turns out to be just the main attraction in a huge and complicated “zoo” of complexity classes. Beyond NP there are even harder classes of problems like “EXP” — the class of problems including figuring out the best move in Chess, that takes exponential time to even check. This whole upper area of problems that are at least as hard as NP-complete is called is called “NP-hard”. There’s also “Co-NP” — the class of problems where instead of being easy to check right answers, it’s easy to exclude wrong answers, which may or may not be the same of NP. And then there’s “P-SPACE”, the class of problems that can be solved given unlimited time, but using only a polynomial amount of space for memory. There are also problems that can be solved probabilistically in polynomial time. That class is called “BPP”, and it may or may not actually be the same as P. And then there’s a quantum computing analog of BPP called BQP. All over the place in here there are complicated little classes that would take a lot of explaining, and, actually some of these turn out to be infinite hierarchies of problems that are slightly more difficult from the ones beneath them. We know there’s an exponential hierarchy and there’s probably a polynomial hierarchy. And out beyond all of this are problems that are, just not solvable by any computer in any amount of time or space. To me, the amazing thing about this whole complexity zoo is that we’re talking literally about what can be computed in a given amount of space, and time. We’re not just looking at the nature of computation here, we’re looking at the nature of space and time themselves. This mess of computational complexity classes, I think, ultimately has implications for physics and biology and, for our basic understanding of everything. As an example of those implications, here’s how Scott Aaronson, a complexity researcher at MIT, explains his intuition about P vs. NP: “If P were equal to NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps”, no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; Everyone who could follow a set-by-step argument would be Gauss.” The world around us, the nature of living things and ideas, of art and genius, is molded around the deep structure of computation. In a very real way, something connected to P vs. NP shows up in the struggles of scientists and artists. Chopin once said: “Simplicity is the final achievement. After one has played a vast quantity of notes and more notes, it is simplicity that emerges as the crowning reward of art.” And Jack Kerouac put it like this: “One day I will find the right words, and they will be simple”.

100 thoughts on “P vs. NP and the Computational Complexity Zoo

  1. Watching this video is classified as P. While finding the proof is NP. But if you had found the proof for P vs NP, claiming 1 million dollars is P.

  2. It's an interesting discussion that I think I could follow if the narrator would just slow down or if I were already an expert in the field (in which case the video would be useless to me).

    The speed of the narrator ruins the video. Too bad.

  3. Hackerdashery — Made two(2) Videos one 6 years ago , one 4 years ago. then stopped. Why did they stop,
    we will never know it may be a simple answer or not ( kind of like P vs NP ).

  4. Actually if P = NP does not mean that all algorithms could be run in reasonable time in our physical world!

  5. Wish I had this video back when I was majoring in computer science. P vs NP was the pinnacle of things I could not wrap my head around in algorithm theory.

  6. Hey,
    Thumbs up for such an elegant way of explaining such a difficult topic.
    Too good. I am positing this url to all the stupid videos which are boring and not able to simply explain the topic, or rather , I should say, they tend to confuse more.

  7. this is a message they begged to be sent to all
    of you mathematicians, physicists, (computer) scientists (2019)

    nvm is  ∞
    our np as p conjecture lost

    annuit coeptis novus ordo seclorum

  8. 1:30 interested in that statement. Has it been 'proved' that there is no fast algorithm for the best chess move?

    Also, if someone proved P = NP, would that automatically provide a way to crack encryption? Wouldn't the proof just being saying "There exists a way…" rather than "I have the way for every problem ever"?

  9. I wish the Clay Institute would add the Twin Prime Conjecture to the list. Very easy to understand the question but very difficult to prove. It's also a very interesting problem indeed.

  10. Haha. I was going to ask who would "thumbs down" this video, but see that is a major topic of discussion. (48K likes and 622 dislikes as of 7/20/2019.)

  11. Not as hard as it seems if you smoke weed. Individuals like me who are psychological adventurers tend to understand very complex questions. I know the answer, but who do I submit it to?

  12. What was the definition of NP again? Seemed unclear to me. Wikipedia mentions something called a non-deterministic Turing machine. A TRUE random generator? Are there really such things? Even quantum mechanics may be deterministic Stephen Hawking wrote and the pilot interpretation of QM is deterministic, so then what is true randomness?

  13. Is it wrong to see it as representing P as a single demonstration of a small piece or the fundamental rule the computer follows and NP as the computer having to perform P many many times in order to represent what we need it to show? And in that case wouldn’t P still equal NP? And the bottom line is that we just simply need a faster computer at some point?

  14. So I have long believed that P is a strict sub-set of NP. There is no solution, but it isn't possible to prove or disprove it. Think Godel's theorem of Incompleteness. Has anyone proposed that yet? Like within the cutting edge theoretical CS circuit? Is that argument taken seriously by experts who spend most of their time on the NP/P sub-expertise?

  15. I don’t think this is very hard to understand, as is everything for me, for I am an extraordinary genius who solves any sudoku puzzle in less than 2 seconds. I believe N=NP, but that must be because I’m an incredible intellectual with huge amounts of terabytes of brain power and cognitive prowess. The mere thought of a problem to hard to solve is a joke to me, one I frequently make with my friends on Fortnite. I would help humanity solve all its problems, but sorry kids, it’s way more fun pwning you on fortnite.

  16. Did anyone notice at 4:09 he classified the question in "P" and "NP" where P has "a quick wat to find them" and NP has "being able to quickly recognise correct answers"

  17. 5:29 "Polynomial" is a terrific word. It refers to the level of terms, or addition and subtraction, which, if you remember, are operations allowable only between identically named terms. Or are you just virtue signalling by dissing our ancestors?

  18. You are WRONG. You claim that mathematically proving things is NP, when it is in fact undecidable, because verifying a mathematical proof is isomorphic to the halting problem. The proof ends with "QED" instead of "end program", that's kind of the only difference. Just because verifying a mathematical proof the sort of mathematical proofs YOU are used to seeing is EASIER than actually proving it, doesn't mean the act of verifying a mathematical proof is polynomial-time in worst case. It is NOT. "Easier to verify than solve" is a vague human subjective description, but easier isn't the same as "polynomial time in worst case". Thus proving math theorems is NOT NP, and in fact a polynomial time NP solver would NOT lead to a magic mathematical proof generator program that can prove anything that can be proved quickly because that WOULD NOT APPLY. And things don't get much worse than "polynomial time" than "undecidable".

    Also, there are actually very few things that a p-time NP solver would actually allow that is useful. Breaking cryptography is pretty much all it would result in. The key is, that in every actual practical problem that is NP complete, first of all, you can find the solution pretty quickly MOST of the time, just not in worst case, and secondly, generally finding an exact solution isn't necessary, but a "good enough" solution that doesn't quite optimize it is often all you care about. For instance, suppose you wanted to fill a disk to capacity and you wanted to pick and choose a combination of files to put on it that would most fully utilize its free space (i.e. the knapsack problem), it's OK if you don't fill it PERFECTLY to capacity, it may be ok if you leave 0.000000002% free space on the disk. And the protein folding thing is misunderstood by the way, it's one of those often-requoted things that is not understood by those quoting it and isn't really what you think it is. Really, destroying public key cryptography is the ONLY important thing that would come about from a P time NP solver.

  19. I wish this channel would produce more videos, the world (and YouTube) needs this type of highly valuable (and also enjoyable) content among these rubbish science-y pile of clutter that seems be more like entertainment minus the science.
    JUST PLEASE MAKE MORE VIDEOS

  20. why aren't there any more videos from this channel? Educational channel such as these shouldn't stop existing. We need them.

  21. Just say Traveling Salesman. Defining a problem is not the same as solving a problem, and P vs NP just means there is no solution. There's only a best guess, based on math. Most people can understand this as "Good Enough". There. I explained it for you. You're welcome.

  22. If you give me a map, three salesmen in Dallas and three destinations, I can mark the correct / shortest routes every time without even thinking about it. Give me 30 salespersons, I can still do it – but it's going to take longer. And I'd be correct in both cases. The first case would be obvious. The second, not so much. But even with 30 I could eventually calculate them all and prove I was right (given a finite number of roads and conditions). But it still falls in the NP domain because I can't give the mathematical proof – because I don't understand how something that was easy for my brain could be virtually impossible to solve with a computer – and prove mathematically. IF we can solve this, then AI will actually work (what we have now is not true AI). And if AI works, human brains will indeed be obsolete. Not sure why everyone is rushing toward this proof – because like Elon said, it will probably spell our demise.

  23. Well, remember that silicon based computer chipsets are limited on how fast they can do calculations. Even if you used GPU cores it would still lack behind on calculations. So, the fact of silicon computers solving ultra hard NP problems isn't a reality unless you had some sort of miracle chip. Sorting out small list is common sense because it take litterly no time to calculate. The larger the caluation the slower. What we have now can only solve a problem one by one causing limitations.

    Quantum computing is to be designed to where it'll layout all possible solutions at once and pick the best solution in a matter of seconds. So maybe our answers to complicated NP won't exist until we have quantum computing and the advancement of A.i and when we have quantum computers, we will unlock way more than what we have. Qubits are much better and faster at solving than bits. that's just my opinion.

  24. Could machine learning play a role in figuring these things out?

    I'm thinking about these two quotes from the video.
    "Even classic video games as Super Mario and Metroid turns out to be connected to NP complete level traversal problems"
    "A fast program to solve any NP-complete problem could be used to solve any problem in NP"

    Seth Bling made a program using machine learning that (after it had been trained) could breeze through randomly generated Super Mario-levels. Now these where straight levels without any path splits if I recall correctly. But we have search algorithms for that, like path finding in mazes which is P.
    I don't know if game speed factors into this as well? Old school games do run in emulators where one could increase the emulated speed, making it possible for a program to complete the levels at it's own limits. There is probably something I am missing as I assume this video present a somewhat simplified version of the problems, or that there was something I missed in the video.

  25. I think that quantum computing might make p=np, but that making quantum programs is an NP problem that can’t be solved in P time without a quantum computer, which means that without quantum computers, p is not np, but once we have them, P=NP.

    I think, maybe.

  26. Great video. One should point out, though, that the internet security apocalypse is not going to happen, not even if P=NP AND a good general algorithm can be found. The conclusion by Scott Aaronson is also completely false.

    Writing music is not an algorithmic problem. For one thing, nobody has found an algorithm that can even write a melody as simple as "Greensleeves", yet, which I would call a much bigger failure of computer science than the P=NP problem. That is truly embarrassing, folks! For another, any and all attempts to set rules for music have to fail as the interesting part about music is the breaking of rules. What each new generation does is to get used to their parents' music to the point that it becomes utterly boring. Then they take what they know and they grind it to pieces and create something new out of it. No algorithm will ever be able to foresee the future taste of people.

    That mathematical proofs like that of Gauss are outside of the algorithmic realm is being taught by mathematicians in an introductory class about mathematical logic. Do I really have to mention Goedel? Jeez, guys, take a break. NP contains a few interesting problems for CS and mathematicians, but pretty much the entire universe that's fun and important for everybody else lives in exp or way, way beyond.

  27. P is not equal to NP, take chess for instance you can teach a computer to make moves in chess based on what the best probable defensive and offensive move would be, but you would never be able to teach a computer to make a move based on the most intuitive defense or offense, given human intuition being the standard. If you look at the complexity of this part problem, it all rests on the inability of the person to mathematically define human intuition.

  28. why is P vs NP considered a problem?from what the narator presented it looks more like a preference rather then something that needed to be demonstrated mzthematically

Leave a Reply

Your email address will not be published. Required fields are marked *