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. Great video…but your pace is very fast. I had to pause many times.

  2. Damn, the time and effort that put in this video must be insane…nice job done

  3. This is the most entertaining piece of media I have consumed for at least two months. Fantastic!

  4. This was really beautifully made, the way you talk, the content you decide to speak about, really made me interested in this area, and the music fits so well and really creates this nice atmosphere

  5. i know the way to solve sodoku fast.only take o(n). Even 100×100

  6. Lovely video. When he pulled up the iPhone I had to verify the upload date.

  7. what makes people confident that p or np are even legitimate concepts/categories/whatever they are in the first place? are people inventing an unsolvable problem by asserting that this is an appropriate description of the phenomena at hand? sorry im sure people must say this all the time. it makes me think of Wittgenstein and how philosophers create problems which were never problems until you articulated it in a way which made it sound like a really pressing problem

  8. Multi Point equal modular number point.
    MP = MNP
    Multi is varietive modular function.

  9. I'll add that I love the style of this video. The chalkboard is a nice touch

  10. Which branch of science someone is required to study at the masters level to learn about this computational complexity?

  11. I have no idea what's going on, but I feel smarter after watching this video.

  12. is it reasonable to expect that a puzzle, such as a 100×100 sudoku grid, to be solvable, would require a set of clues, a starting point? …how does that mirror real life? …is it equally reasonable to assume the same set of rules, as in a set of clues, with protein folding? …i really don't know, i'm simply curious. a very provocative video…i've watched it a few times. a fascinating dilemma.

  13. This is probably the best computer science related video that I've seen , this channel deserves more than 2 videos .

  14. Thank you for making this video, understood more here than what my professor was teaching. Ask him resulted in a huff and email me later lol…

  15. P Vs NP is an “NP problem” and since you can’t solve an NP problem efficiently without a NP solution… you can’t solve p vs np efficiently in its current framing.

    If anyone can reframe the problem in a way we can get a solution to, it can be solved.

    We are currently stuck in circular reasoning in p vs np and that mental block is the same flaw that computer programmers are stuck in when they try to write a sodoku solver.

    It may be something about our mental wiring or how we perceive time itself that has an actual blind spot in our thinking and we effectively need a paradigm shift.

  16. Youre probably not gonna read this, but i loved it. Ive seen the term
    P != NP before so im really glad to have found an explanation

  17. It is nice to make list of the 7 hardest problems and revard them with a million dollars.

    It is a slap in the face to humanity that spends bilions on alkohol and cigg.

  18. If you managed to make a computer or something that could solve anything then you could solve all of the other millennium problems and it is probably best for somethings if they stay either unsolved or very hard to solve.

  19. We talked about this in my artificial intelligence class, but it was completely disconnected from the other topics we were discussing and not explained very well. Noone understood why we were discussing it and we found it very mundane. Now I just stumbled across this video and holy sh*t you have awoken my interest in this topic! Great job and excellent video!

  20. God this guys video about the chess analogy went out the window with Google’s that only checks 80,000 moves a second instead of other programs that check millions and has all the best moves and cannot lose, only win or draw

  21. How about this for an EQUATION. Stop having BABIES!!!!!!! THAT IS THE BEST 1 OF ALL

  22. You guys speak of QUANTUM computing. OK. THAT IS FINE. IF THAT IS TRUE. BUILD A QUANTUM COMPUTER THAT CAN ANALYZE QUANTUM EXPERIMENTS OR EQUATIONS???? OH, I GUESS THE UNIVERSITYS WOULD LOOOOOOS. MILLIONS IN THERE SO CALLED PHYSICS DEPARTMENT'S. HOW HARD WOULD THAT BE. ACTUALLY THAT WOULD BE THE VERY BEST. I GUESS THER ARE TO MANY VARIABLES TO SALV

  23. but is this just for finding an optimal method in completeing something a certain way? like unscrambling a rubiks cube, solving in the least moves, or solving it the fastest etc. being most optimal in a sudoku puzzle or solving it the fastest possible, or being the most effcient? for finding the best chess move in 1 shot would mean ruining the whole reason of continuing a comp game which is the extreme counter to perfect play, which is impossible if both players play perfectly. theres no such thing as a 1 win move in chess or any comp game unless you literally broke the boundaries hence broken. theres the safest play and plays that lead to mind games or setups etc. or in a certain specific situation moves that would create an advantage, have a better position in theory than the opposition, help win the game. also what does this have to do with computer science or is it just a random theory part of the topic that got a lot of recognition?

  24. I think we'll just have to wait a few decades untill we've discovered AI that is close to perfect and feed these problems to it. My guess is that we will create/simulate an AI as smart as an average human brain (IQ 100) around 2060 and a smart brain such Einstein (IQ 160) by 2090. So eventually we'll solve them all. Just not with brute force.

  25. If you’re going to make a video about P versus NP, you should really avoid saying the phrase “a problem in P”

  26. As a CVRPTW guy, well put. Anyone interested in solving the N vs NP problem should know there's a million dollar reward for doing so.

  27. I can solve NP problems, so can you actually.

    Just gotta kill Bowser

  28. "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." – Chopin (that’s a nice quote 10:23)

  29. I don't really know anything about this topic, but the video is pretty cool.

  30. I wonder if it's even possible objectively to prove this … thing? what is the conjecture? "P=NP"? and how is the proof even going to look like?

  31. This one will never be solved out of all the Millennium Prizes imo

  32. maybe simplicity is not the holy grail : https://blogs.sciencemag.org/books/2018/06/04/lost-in-math/

  33. Self-learning AI: let me introduce myself
    quantum computer with Self-learning AI: step away smol boi, this thing is for big bois

    sorry, but AI does know the answer to the chess question… at least good enough move

  34. P vs NP problem in a nutshell: How can I prove all rocks(problems) are solid(p)? Well, this rock seems not solid? Maybe is not a rock.

  35. 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.

  36. 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.

  37. 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 ).

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

  39. TUDTRNGCHURCHBFCOOKLEVINLTFBQPNPUBELHMAEPS
    No, I haven't found any meaning in it yet.

  40. 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.

  41. 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.

  42. 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

  43. Okay seriously this was the best video I have seen in my entire life. You got all of my appreciation!

  44. if u find out, dont tell anyone because it cost less to kill you than it is to pay for the damages of encryption.

  45. 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"?

  46. 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.

  47. I hardly understand but I feel motivated to crack it for humanity!

  48. 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.)

  49. 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?

  50. 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?

  51. Outside of all these problems is figuring out the best thing to say to a girl you like.

  52. Amazing video. But I REALLY wish you could clean your blackboard.

  53. 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?

  54. 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?

Leave a Reply

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