▶︎ 0:01 In the last episode, we laid the difficult groundwork to really seriously discuss the P versus NP question, which is what we're going to do in this episode. Just to recap, last episode, we had two big ideas. We introduced two super important concepts. The first one was the identification of what intuitively is an easy problem, with problems that are solvable by fast algorithms. And we also identified fast algorithms, with polynomial-time algorithms. And we talk about P versus NP. The P stands for polynomial, in polynomial-time algorithm.
▶︎ 0:40 And remember, the right way to think about a polynomial-time algorithm is really how does the problem size you can solve scale as your computer gets faster and faster? Maybe you have a time budget of a minute to solve a problem. You buy a computer that's twice as fast, and the question is, how much bigger a problem can you solve than before? And with a polynomial-time algorithm, you get a percentage increase in the size of the problem you can solve in a given amount of time with a more powerful computer.
▶︎ 1:05 For example, with a linear-time algorithm, every doubling of computer power gives you a doubling of the problem size that you can handle. If you have a quadratic-time algorithm, that would be like the grade school method for multiplying two numbers. Every doubling of computing power would give you a 41% increase in the size of the problems you can solve, and so on. That's what we mean by a polynomial-time algorithm, and easy problems or problems in P are those that are solvable by a fast algorithm, in this sense.
▶︎ 1:35 The second super important concept that we introduced in the last episode was that of an NP-complete problem, and we're identifying seemingly hard problems with these NP-complete problems. And so what does that mean? That means a problem where on the one hand it's very easy to check if the solution is correct. So again, think about Sudoku. It may be hard to compute from scratch a solution to a Sudoku puzzle, but if someone else does the work, and then shows you the results, it's very easy to say, "Oh, good job. That is indeed a valid solution to this Sudoku puzzle."
▶︎ 2:08 That's what we mean by an NP problem, a problem where it's easy to check a solution if someone hands it to you on a silver platter, and then specifically the NP-complete problems are the hardest problems in NP. So they are as hard as any other problem where it's easy to check the correctness of solutions.
▶︎ 2:30 And at the end of the last episode, I reminded you what it means to say one problem is as hard as another. It means the same thing it meant back in episode one when we were talking undecidability. It means that one problem reduces to another. If all you need to do to solve problem A is to solve problem B, then problem A reduces to problem B. In that sense, problem B is at least as hard as problem A because it allows you to solve problem A.
▶︎ 2:57 And we also highlighted that all NP-complete problems therefore share the same computational fate. Either all of them can be solved by efficient algorithms or none of them can be solved by efficient algorithms. They are all really thinly disguised versions of the same problem.
▶︎ 3:16 There's only two possible worlds we could live in. The ones where all the NP-complete problems are in P, are efficiently solvable, and the world where P and NP are different, and all of the NP-complete problems are not efficiently solvable. And if you think about it, these two themes, on the one hand problems in P, solvable problems, and then NP-completeness, so problems that appear to be unsolvable, these directly relate to what I would call the two big and complementary themes that run through this entire five-episode series.
▶︎ 3:50 The two themes being, first of all, what computers can do, and here, again, with P, we're scaling that down to ask, what can computers do efficiently? And then the second big theme being, what is it that computers cannot do? And again, in this part, we're scaling down to asking specifically, what can they not do efficiently? But as it's been since the very beginning of this series, we're thinking about, on the one hand, the power of computation or currently efficient computation, and then, on the other hand, the limitations of computation.
▶︎ 4:24 Both of those themes are obviously already there in Turing's 1936 paper, the introduction of Turing machines to express what computers can do, the undecidability arguments to express what they can't do. Both of those themes, super, super important. They have a symbiotic relationship, work on what computers can do and forms our understanding of what they can't do, and vice versa. And what's cool is this P versus NP problem, it's where these two different themes meet each other, and where we're a little bit stuck in both of the two themes.
▶︎ 4:59 So think about P versus NP, we don't know the answer, so maybe they're the same, in which case there's just gonna be fast algorithms that we don't know about yet. Or maybe they're different, in which case there's ways of establishing limitations on algorithms that we don't know about yet. So either we need to have a better understanding of what it is that computers can do efficiently, that's in the event that actually the right answer is P equal to NP, we need new fast algorithms that we don't currently have, or we need better understanding of what it is that computers cannot do efficiently. That's in the event that the actual answer is that P is different than NP, in which case we need new ways of proving limitations. So we need more progress on one of the two themes, but we don't know which one. The progress on one of those two themes is going to be what resolves this P versus NP question.
▶︎ 5:47 Before we go deep on this P versus NP question, let me take some time to talk through the backstory, some of the history leading up to it. We didn't really have time for much historical discussion in the last episode. But the short version, which I'll elaborate on, is that in the mid-20th century, so 1940s, 1950s, 1960s, these two themes, work on what computers can do, that is the design of new algorithms, and work on what they can't do, that is the invention of new ways of proving limitations on them, those two lines of research really developed largely independently, by largely distinct groups of researchers, until they collided in the late 1960s and early 1970s with the articulation of the P versus NP problem.
▶︎ 6:34 And this, I think, is just really cool, so I'm going to spend some time on it. You have this parallel evolution of people thinking about what they can do and what they can't do, and at some point they realize they're stuck at exactly the same place, the P versus NP question. To go into a little more detail on that, since Turing's paper, I'm speaking in 2026, so Turing's paper was literally 90 years ago, and over those 90 years, I would say a majority of theoretical computer scientists, not all, but most theoretical computer scientists have tended to specialize in one of these two themes, either in understanding the power of algorithms or in focusing on their limitations.
▶︎ 7:17 So the researchers in the former camp that think about what algorithms can do, sometimes they focus on what they call possibility results or upper bounds, and they might say they're algorithms researchers. That's how they might describe themselves. And then there's a historically somewhat distinct group of theoretical computer scientists that focus on limitations of computation or impossibility or negative results, and those researchers might self-identify as complexity theorists or as lower bounds researchers, because they're focused on difficulty, proving levels of the difficulty of what problem complexity is.
▶︎ 7:59 Now, this dichotomy, obviously it's an oversimplification. Many theoretical computer scientists, especially the most famous ones honestly, defy easy categorization and make contributions to both of the themes. But that's still a useful almost like sociological grouping of researchers in this area you might want to keep in mind.
▶︎ 8:20 And in fact, it's funny, because if you're not hanging out with mathematicians, it's not part of your day-to-day existence, from afar, mathematics probably seems, by design, much more than most disciplines, it seems like this logically unified field. It's like, there's the basic axioms that almost everyone agrees upon, and everyone's just exploring the consequences of these axioms. But in practice, actually mathematical researchers, they really do tend to cluster themselves in groups according to the methodology that they tend to use. And as mathematics or mathematical fields get more and more mature and advances require deeper and deeper specialization, you see this fragmentation more and more.
▶︎ 9:07 So there really are lots of different sub-communities of mathematical researchers that tend to be bound by, again, common methodology, a similar toolbox for making progress. And the toolbox for proving limitations on computation, for proving impossibility results or lower bounds, that's historically rooted in logic. So remember in episode number one, we talked about Gödel's incompleteness theorem being this important precursor to Turing's work on undecidability, and that's still to some extent true. Lots of other techniques are used in proving limitations as well, but it's still a little bit in that old logic tradition, and as a result, the researchers that tend to be drawn toward proving impossibility results, establishing limitations, those researchers, again, oversimplifying, but they often have a bit of a pure mathematics mindset, I would argue.
▶︎ 9:59 Now, the flip side of the coin, possibility results, algorithms, that's just as important. Like we've seen with Karatsuba's mind-boggling multiplication algorithm, there's brilliant work to be done on the unexpected things computers can do, and that's a different type of work. So those contributions, like Karatsuba's contribution, often requires deep insight into the structure of a specific problem. For example, locating redundant work, that's being used in a straightforward solution, and then exposing the redundant work so it can be reused rather than recomputed. So that would be clever ideas that you put in an algorithm to take advantage of the problem's specific structure.
▶︎ 10:43 And so for this reason, again, oversimplifying, researchers in algorithms who prove upper bounds, they tend to have a little bit more of an engineering mindset, a problem-solving mindset rather than a theory-building mindset. Again, just speaking purely on average. So for example, we can actually go back through our cast of characters thus far, and it's a fun exercise to classify them. Of the people we've talked about, the computer scientists and the mathematicians, which ones fall more into the algorithms or upper bounds category, which ones more in the impossibility results or lower bounds category? Or which ones don't fall neatly into either of those? So let's just think back over the different researchers we've talked about, thus far.
▶︎ 11:30 Let's do it this way. Name, and then let's classify them as either algorithms, if they focus on what computers can do, or lower bounds, if they're more interested in limitations on what computers can do. Obviously I'll go roughly chronologically as far as the contribution that we discussed of these researchers.
▶︎ 12:02 1936 was our starting point, Turing. And Turing's definitely one of the hardest to classify researchers. I encourage you to read a lot more about him if you have time. Very interesting. For our purposes here, for this series, because we're zooming in specifically on his development of the theory of undecidability, I'm going to classify Turing as a lower bounds researcher. But I'm going to put an asterisk, just to indicate that in fact Turing actually by all accounts had a bit of an engineer's mindset some of the time, constantly tinkering with various machines and physical experiments and random stuff inside rooms. Really very much a generalist. But again, for our purposes today, really a lower bounds person.
▶︎ 12:50 I guess we talked about Church at the same time. Church was really a pure logician, so I'm just going to leave him off the list. We talked about Von Neumann a couple times. So for example, in the late '40s working on projects like the EDVAC and the ENIAC to realize general purpose computers. Again, very, very difficult to classify. For our purposes today, Von Neumann has a number of amazing results in pure mathematics. For our story, it's primarily on the "let's build computers and make them work," the engineering mindset. So let me again here put algorithms with an asterisk.
▶︎ 13:24 So for example, actually even back in 1945, which is where they were starting to dream about computers but hadn't really started building them yet, Von Neumann invented what's a super famous algorithm, called mergesort. When I teach algorithms at university, lecture number two is mergesort, and that Von Neumann came up with before really the computers he was working on had been built yet. But again, very, very broad, Von Neumann.
▶︎ 13:51 So who else did we talk about? Another thing we talked about in the late '40s would be Dantzig, George Dantzig, famous for the simplex method. Also famous for walking in late and seeing the two problems on the board and solving them thinking they were homework, that was also Dantzig. So simplex method was late '40s, and Dantzig's a great example of really just an algorithms person. Dantzig really wanted to help people quickly solve problems that were important for the military, for business, et cetera. So this is classic algorithms, I would say. George Dantzig.
▶︎ 14:26 So late '40s and then, for example, in the 1950s was thinking hard about the traveling salesman, salesperson problem, and so on. We talked about Edsger Dijkstra, who again, did a ton of stuff all over computer science. For example, probably best known for trying to turn programming into more of a science than an art. For example, using a lot of logical methods, so that you could write programs that you could then prove correct. He did a lot of other stuff. In particular, for our purposes, he came up with Dijkstra's algorithm for computing shortest paths. So let's put him in the algorithms camp, and maybe again with an asterisk just to indicate the breadth of his contributions.
▶︎ 15:12 Now, the other algorithm we talked about in the second episode was Karatsuba's method for multiplying two integers. And we talked about how Karatsuba was attending a research seminar by Andrei Kolmogorov. So let's put Kolmogorov on here. This would've been ballpark 1960. And at this point, really computers were being built and really being used, and Kolmogorov was an early serious mathematician that was taking seriously the mathematics of understanding the optimal way to perform certain computations. Kolmogorov was focused largely on the lower bound side, I will say.
▶︎ 15:49 You'll recall that his conjecture, which is the thing that catalyzed Karatsuba to invent his method, Kolmogorov conjectured you could not beat the straightforward quadratic time algorithm that we all learned in grade school, and Kolmogorov was interested in the lower bound showing that you couldn't do better. Karatsuba then obviously blew up that conjecture by giving an algorithm that you could do better. So Karatsuba I'm actually not going to put on this list. Actually, if you look into Karatsuba, he was really just like a pure mathematician, mostly a number theorist. As far as I can tell, his integer multiplication algorithm was just like a pure side quest that came out of the seminar by Kolmogorov that he was studying, which is wild. So he in some sense was neither, but Kolmogorov, who was running that seminar, definitely focused on the lower bound side.
▶︎ 16:35 Who else? We mentioned Alan Cobham. This is when we were talking about identifying the notion of efficient computation with computations that require only a polynomial number of steps, the idea that the appropriate criterion for efficiency should be that with a doubling of the computing power, you should get a percentage increase in the problem size that you can solve. So Cobham was one of the two people, at least two people, maybe more, that proposed that idea. Cobham, honestly not that much is known about Cobham, and his publication record is pretty sparse, but based on what I know, my best guess is he was primarily a lower bounds researcher.
▶︎ 17:17 But then the other person who came up with this idea of polynomial time around the same time was Jack Edmonds, who really cared about algorithms. Edmonds has some of the really most incredible algorithms and networks we have to this day. In particular, a lot of beautiful algorithms around what are called matching problems. So basically if you have a bunch of objects or you have a bunch of people and you would like to pair up the objects or pair up the people in particularly good ways, Edmonds was really the person that came up with the initial wave of powerful matching algorithms. And then in particular when he got stuck on the shopping salesman problem, he conjectured that there was no good, and again, he meant polynomial time algorithm for it. But that's really, he was really focused, he was really an algorithms guy, is an algorithms guy, I should say.
▶︎ 18:09 And then we concluded with the Cook-Levin theorem. So we have Stephen Cook at Berkeley but then moving to Toronto, a very much a lower bounds person. Really rooted in the traditions of logic and of Turing. Less interested apparently, it would seem, in specific problems, specific algorithms for specific problems, much more the theory, like the theory of NP-completeness.
▶︎ 18:44 And Levin, Leonid Levin, so I mentioned that he was doing his work behind the Iron Curtain, I don't think I mentioned that his first PhD, he got a second one when he came to the States at MIT, his first PhD from Moscow State University, the same location of that research seminar that Karatsuba was attending, and his advisor, Levin's advisor was, wait for it, Andrei Kolmogorov. And so Levin basically inherited the lower bounds mindset from Kolmogorov, it would seem. This was about a decade later after Karatsuba.
▶︎ 19:25 And so I'm sure some of my friends would quibble with some of these classifications, but going back through the cast of characters that we've seen thus far, that's how I would put them. That's the camp that I would put them in.
▶︎ 19:41 Why did I do this? One is it's just fun. We've already talked about a lot of fun stories and a lot of famous names in mathematics and computer science, but the main reason I did it was really just to give you the historical backdrop for the articulation of the P versus NP question. Again, you had researchers focused really on algorithms, figuring out ways for computers to solve particular problems faster and faster, and then you had researchers more with the engineering mindset, and then from more of the pure math mindset, you had researchers focusing on lower bounds, trying to establish limits on what could possibly be done with algorithms.
▶︎ 20:18 And through the '40s, through the '50s, through the '60s, these two threads of research evolved largely independently. Largely by different groups of people. There are points of contact. So Cobham and Edmonds independently came at the same concept of polynomial time computation, as a way to express efficient computation, but these were largely distinct, largely evolving independently.
▶︎ 20:45 Now let me add one more name to the list. It's a name I mentioned briefly in the last episode, but I didn't really say what his contributions were, and that's Richard Karp. Richard Karp, very much an algorithms person. And responsible for a number of breakthrough algorithms in the 1960s, 1970s, 1980s, spent most of his career at Berkeley where he's a professor emeritus now. For example, he actually has an early paper on what's known as the maximum flow problem with Edmonds from the early '60s. Honestly, when I teach algorithms, I still teach tons of stuff from that old paper. It's from the early '60s.
▶︎ 21:34 Point being is at the time NP-completeness came out, from Karp's perspective, Karp is in Berkeley, so he doesn't know about Levin's work. Levin's work wasn't going to reach the States or North America for a while, over a decade. But Cook was at Toronto at this point. So 1971 was when Cook published his version of the Cook-Levin theorem, and so Karp at this point, he'd been around. He was, I don't know, he's probably ballpark 40 years old, something like that. He'd spent well over a decade trying to come up with fast algorithms for lots of different problems. Many of them, he succeeded. Like I said, I still teach many of his algorithms today. Some he didn't.
▶︎ 22:18 So Karp, like Dantzig, got obsessed with the traveling salesperson problem, and spent a lot of time trying to come up with a fast algorithm for it. In fact, I don't know if you remember, the last episode I said you actually can improve over exhaustive search for the traveling salesman problem. There is some redundant computations you can isolate and reuse, and that's in part Karp's work that shows that. So he did improve over exhaustive search for the traveling salesman problem, but he could never find a fast or polynomial time algorithm despite a lot of effort.
▶︎ 22:51 And, again, as a very seasoned in-the-trenches algorithms researcher, he knew off the top of his head lots of other problems that looked so similar to the problems he did know how to solve, looked so similar, and yet neither he nor anyone he knew knew how to come up with fast solutions for them. So Karp knew off the top of his head all these different places where he and the broader algorithms community were stuck.
▶︎ 23:15 So what that meant was that in 1971 when Cook's paper came out and Karp read it that same year, he read it soon after publication, on the theory of NP-completeness, that name didn't exist yet, we'll talk about that in a second, but on what would come to be called the theory of NP-completeness, Karp immediately recognized Cook's theory as a solution. See what I did there? A once in a generation unlock that simultaneously explains the barriers that were being encountered by all the researchers that were stuck on all these problems, himself included.
▶︎ 23:51 So for the first time, Karp had a scapegoat. He could say, "It's not that I'm just having a bad day and I'm not smart enough today to come up with a fast algorithm for the traveling salesman problem." He immediately recognized Cook's new theory as the explanation of why he and all of his colleagues were stuck where they were stuck.
▶︎ 24:10 Now, Cook's paper itself actually only established the NP-completeness of two natural problems, one problem called satisfiability, which is a problem in logic, and another problem called subgraph isomorphism, which is a problem in networks. And I don't know this for sure, but I could imagine that to a complexity theorist like Stephen Cook, perhaps he viewed his main work as done. The theory has been built and it's really for others to then apply the theory to specific problems.
▶︎ 24:42 Karp meanwhile, as an algorithms researcher, was very happy to take the torch from that point. So Karp, as an algorithms person, took Cook's theory, and the demonstration of these two problems that you could establish NP-completeness for, and through reductions, spread this idea of NP-completeness to many, many, many other problems, including all of the ones he'd been trying to solve for the last 15 years, and so far had failed.
▶︎ 25:11 So Karp, this was clearly a very exciting time in Karp's career. He's written about it. For all of 1971, after he read Cook's paper, for a bunch of 1972, he was basically full-time just bouncing ideas off anyone he could talk about. So he was constantly trying to come up with new reductions between different pairs of problems, showing more and more problems, other than Cook's original, to be NP-complete. There were meetups. This, again, was early '70s. There were meetups in the San Francisco Bay area where all the theory computer science nerds would get together and Karp would try out these different reductions he was working on.
▶︎ 25:50 And then finally, the big reveal was, I think in mid 1972 or so, there's a symposium at IBM, the research lab, which is still there today, up there in Yorktown Heights, and Karp revealed a list of 21 NP-complete problems. So Cook had two, and Karp had enlarged that list to 21. And very satisfyingly for him, among those 21 indeed was the traveling salesman problem.
▶︎ 26:16 So Karp did show that TSP is NP-complete. So if NP-complete problems do not have fast algorithms, then that's the explanation for why Dantzig, Edmonds, Karp, you name it, had failed to find a fast algorithm for TSP, up to that point. And that was really the big bang, honestly, for NP-completeness. It's not like experts were definitely well aware of Cook's paper, but Karp took what was really a lower bounds paper and showed that actually this explains everything that's going on also for the algorithms researchers.
▶︎ 26:51 So all of a sudden, even if you'd never read any papers ever on the limits of computation, you wanted to now know about NP-completeness just so that you could justify your failures on problems you've already failed to solve, and so that you could not waste time on other problems that turn out to be NP-complete and where you don't expect to have a fast solution. So with Karp's demonstration, it became clear to everybody, everybody that NP-completeness would revolutionize our understanding of efficient algorithms and their limitations. And moreover, while the theory by itself does not resolve whether NP-complete problems are efficiently solvable or not, it takes what would seem to be many different open questions, like for the 21 problems on Karp's list, 21 different open questions about whether that problem admits an efficient algorithm or not, and boils that down into what turns out to be just one open problem. Again, with NP-complete problems, they all share the same computational fate. Either all 21 of Karp's problems are efficiently solvable or none of them are.
▶︎ 27:55 So before I go back to the whiteboard and remind you of the pictures we drew of these two different worlds that we talked about last episode, just a quick personal note, which is one of the cool things about being a computer scientist or just more generally working in a relatively young field is it means if you're lucky, you will actually have the opportunity to meet some of the early researchers that shaped how the field has evolved.
▶︎ 28:20 And so I've been tremendously lucky that way. I've met all of Cook, Karp, and Levin, all of whom are still alive. And in particular, there's a big conference every year in theoretical computer science called STOC, S-T-O-C. And in the 2021 version of STOC, that was the 50th anniversary of the Cook-Levin theorem, so it was an idea of Stefano Leonardo's that we assembled an anniversary session of the Cook-Levin theorem.
▶︎ 28:48 And so I was the moderator, and Cook, Levin, and Karp all participated, and it was very, very cool to hear all three of their recollections of what life was like at that time. And of course, Levin talking about working alone in the Soviet Union, not knowing about the work that Cook and Karp were doing, on this side of the Iron Curtain. So that's easy to find on YouTube. I encourage you to check it out.
▶︎ 29:09 So let me remind you how to visualize
▶︎ 29:13 This now unified open question about whether all NP-complete problems are efficiently solvable or whether none of them are. This is the same picture from the last episode. Basically, we're in one of only two worlds. That's the power of NP-completeness and the universality of NP-complete problems. There's only two possibilities. They're very different, and we don't know which one we're in, which is frustrating and maddening, but the world either looks like this thing on the left or it looks like the thing on the right.
▶︎ 29:41 To remind you, on the left, this is the world as Edmonds envisioned it when he conjectured that there's no polynomial time algorithm for the traveling salesman problem. What I've drawn here, this is all NP problems. These are all problems for which you can recognize a solution easily if someone shows you one. All problems that are solvable by efficient algorithm, all problems in P, that's a subset of NP. So these are going to be the easiest problems in NP down at the bottom.
▶︎ 30:11 The way Edmonds was thinking about it was, you've got problems like computing shortest paths, you've got Dijkstra's algorithm, that's fast. So this is an easy problem. This belongs down in the P region, polynomial time solvable, and according to Edmonds' conjecture, the TSP, while still being easy to check solutions. If someone shows you a way to visit all the rides in an amusement park and it takes only 30 minutes, that's straightforward enough to verify, so it belongs in NP. So Edmonds was conjecturing that that's something that's in NP but outside of the easy part of NP, not efficiently solvable.
▶︎ 30:45 Now with the Cook-Levin theory, we have this notion of the special case of NP problems that not only themselves have efficiently verifiable solutions, but in fact are universal, encode every problem, every NP problem. Every single problem for which you can efficiently recognize solutions is in effect a special case of an NP-complete problem, and indeed, the TSP, as Karp established, is one of those NP-complete problems. So this was Edmonds' view of the world.
▶︎ 31:15 On the other hand, if anyone ever finds even one algorithm for even one NP-complete problem, everything collapses. These all share the same fate. So if you can pull one of these into the easy region, all of this goes into the easy region, and we live in World Number Two, the world where there are generic algorithmic shortcuts for all problems, where solutions are easy to recognize. Whenever you can recognize solutions, you can also find one far more quickly than you might have originally expected, far more quickly than you would through exhaustive search.
▶︎ 31:50 So P versus NP, what is it? It's literally just the question, do we live in World Number One or do we live in World Number Two? So P versus NP.
▶︎ 32:03 This is just World Number One versus World Number Two. And here, World Number One corresponds to the P not equal to NP case, where P and NP-complete problems do not overlap. And World Number Two is where everything collapses, P equal NP. So that is the P versus NP question.
▶︎ 32:36 And again, conceptually, is an algorithmic shortcut like the one we saw in the shortest paths problem and the one we saw taken advantage of by Dijkstra's algorithm, is that algorithmic shortcut somehow very problem-specific? Is that just about shortest paths? Or are algorithmic shortcuts everywhere? Are they ubiquitous, shared by literally every single computational problem where you know a solution when you see it? That's not all problems in the world, the halting problem is not an NP problem. But almost all of the problems that we encounter in day-to-day life, indeed there are easily recognized solutions. You know a solution when you see it.
▶︎ 33:14 So I hope the P versus NP question sounds like a pretty important question. There's all these NP-complete problems, including lots of problems we would love to be able to solve, either they're all solvable or they're unsolvable, which is it? We all wish we knew. We don't know. This is an open question. Either could be true. Most people have their thoughts about which way they think it's gonna go. Most people will believe that we're actually in World Number One, that P is different than NP, but that has not been mathematically established.
▶︎ 33:46 So it is an extremely important problem and it's now widely recognized as such. Back in episode one, when we were filling in the backstory for Turing's work, we talked a bit about David Hilbert, and we talked about how at one of the first International Congresses of Mathematicians, ICM, the one in 1900 back in Paris, that Hilbert used the occasion of his keynote lecture to propose 23 open mathematical problems that he thought people should work on, one of those being the problem that Turing resolved in the negative, in his 1936 paper. And in 2000, so a hundred years later, the Clay Mathematics Institute issued what they called the Millennium Problems. So this is a list of seven open mathematical problems, where at the time all seven were open. Since then, one of the seven has been solved, the other six remain open. And I think rightfully so, the P versus NP question was included as one of those seven problems.
▶︎ 34:52 You might have heard of some of the other ones, like the Riemann hypothesis, or Navier-Stokes equations, or the one that has been solved actually, the Poincaré conjecture. So those are other examples of problems on that list. So at this point, P versus NP, it really is a mainstream opinion that it's one of the deepest, most important, open questions in all of mathematics. If you wanna know more about these Millennium Prizes, actually I just noticed, so the 25th anniversary of the 2,000 problems was last year, I'm speaking now in 2026, and the Clay Mathematics Institute actually just posted a bunch of videos by famous computer scientists and mathematicians giving updates on progress on each of those seven questions. So P versus NP particularly, you can see a lecture by Avi Wigderson, the legendary theoretic computer scientist, talking about the current state of the art of that problem.
▶︎ 35:41 So what happens if you solve one of these Millennium Prize problems? Well, fame and fortune. Fame for sure, fame for sure. Fortune I guess is all relative. So the amount of prize money is a million dollars, which in some ways is a lot, but if I think about just how important these problems are and how amazing, how big a deal it would be if they were resolved, one million to me now just seems way too low. So if there's any billionaires listening to this looking for some philanthropy, you might wanna consider supplementing the Clay Mathematics Institute prize fund to get to maybe 10X those prizes that they're offering for the Millennium Prizes, including P versus NP.
▶︎ 36:22 Anyways, like I said, one of the questions has been resolved, the Poincaré conjecture, and I talked in episode number one, it's like shooting a fish in a barrel to talk about strange behavior by mathematicians, and believe it or not, the person who solved the Poincaré conjecture refused to pick up the $1 million prize from the Clay Mathematics Institute. So they still have all $7 million in the bank as far as I know. So I told you earlier that I would tell you some stories about the alphabet soup and the P versus NP conjecture.
▶︎ 36:55 After Karp popularized Cook's work, and again, remember, Karp was unaware of Levin's work at this time, so he was just based on Cook's work, and greatly expanded its scope by showing that it wasn't just a couple of isolated examples of NP-complete problems. Actually, there are going to be tons of them. So once Karp made that clear, everybody wanted to know the answer to this question. Is there fast algorithms for all of Karp's problems, or are there not-fast algorithms for any of them? And at that point it became clear this was going to be a very fundamental question in theoretic computer science, and so everybody agreed, we need some good terminology to speak about this big open question, which we now understand.
▶︎ 37:35 In Cook's 1971 paper, he definitely talked about the concepts of P, problems solvable by polynomial-time algorithms, and NP, problems with easily checked solutions, without actually introducing any succinct terminology for either of those concepts. So it was Karp, when he released his 21 problems and released a paper describing them, it was in that paper that he introduced the terminology P and NP for those concepts. And they've stuck ever since. So again, P meaning it's for polynomial, because they're problems that can be solved by a polynomial-time algorithm.
▶︎ 38:11 The NP for, wait a minute. I guess I never told you anything about what NP might stand for. Actually, there's a reason for that. People like to ask this until they hear the answer, and then they're sort of sorry that they asked the question. The biggest thing I want you to know about NP is what it doesn't stand for. This is the rookie mistake. The rookie mistake is to think that it stands for not polynomial. P and NP, polynomial/not polynomial. That is not what it stands for.
▶︎ 38:44 If you really must know, it stands for non-deterministic polynomial. Maybe a few of you have heard about non-determinism than you would have a few years ago, because now with modern machine learning algorithms, you're starting to hear more and more about non-determinism, the idea that an algorithm might do different things with the same input as you run it multiple times. Anyways, turns out non-determinism is a different equivalent way to express the idea of efficiently checkable solutions. And that is the modern way of thinking about NP problems. You know a solution when you see it. So NP, non-deterministic polynomial, bit of an anachronistic phrase. But that's what NP stands for.
▶︎ 39:25 So you're like, "Okay, cool. I guess I understand the P, understand the NP. What about NP-complete?" So what's up with that? And if I take a step back and try to put on an outsider's shoes, it does feel like a hopelessly inscrutable term. It just doesn't have a lot of content immediately there, from the phrasing, which really does a disservice to the fundamental concept that it defines, because I think the concept is fundamental and deserves widespread appreciation and wonder, even.
▶︎ 39:59 We talked about how it's amazing that these NP-complete problems even exist. You can have universality. One problem that's a proxy for many. So mathematically, the convention is that you would call a problem X-complete, for some set X, if the problem is both in X and then also is as hard as every other problem in X, or as hard, as usual, it is defined using a reduction.
▶︎ 40:25 And so that's what it means. Believe it or not, some thought was put into what the name of this concept should be. Again, Cook himself did not give it a name. And Levin was not part of this conversation, 'cause again he was in the Soviet Union. Don Knuth, without doubt one of the most famous computer scientists of all time, known for his Art of Computer Programming books among many other things. Don Knuth, if I put him on this list, he would also be primarily an algorithms person.
▶︎ 41:00 But like Karp, he immediately recognized how important this new theory was going to be that Cook had developed. And Knuth has written these textbooks, and he really shaped a lot of the field of computer science in the '50s, '60s, and onward. Knuth had given names to lots of things, so he knew the importance of giving things good names. That really the science can actually be more successful if things are named in attractive ways. So he basically crowd-sourced suggestions.
▶︎ 41:30 We're talking about 1974 now, so he can't exactly post on Twitter for suggestions or anything like that. But there was a newsletter that all the theoretic computer scientists read called SIGACT News. And Don Knuth put out a call for suggestions for what should we call what we now call NP-complete. So at that time, NP-complete was one option. Knuth wanted to hear about some other options.
▶︎ 41:55 The broader scientific community answered Knuth's call and wrote in some suggestions. Let me tell you some of the highlights. Again, this is 1974. Some of the other more serious proposals included, again this is what we now call NP-complete problems, what else might they be called? Herculean, which again sort of presupposes that P not equal to NP, so it's a little dangerous, but Herculean, formidable, and arduous. All of those share the same problem. They kind of presume that P not equal to NP is the right answer.
▶︎ 42:29 Some less serious write-in suggestions included hard-boiled, so that was in homage to Steve Cook, was sort of the intention. And then you can kinda tell this is the 1970s when Albert Meyer suggested the word hardass, allegedly standing for as hard as satisfiability. That was his alleged abbreviation. One very cute one, a researcher named Shen Lin suggested PET, P-E-T, all capitals, because it was sort of a pleasingly flexible acronym, depending on how P versus NP panned out.
▶︎ 43:07 So possibly standing for probably exponential time. This is before the P versus NP problem is resolved. Again, that presupposes a prior, but most people have that prior, that it's more likely that P is not equal to NP. And then if P not equal to NP is actually solved, PET could stand for provably exponential time. There's a quibble there, but let's leave it aside. And if for some reason P winds up being equal to NP, then it could be previously exponential time. So that was Lin's suggestion.
▶︎ 43:37 Anyways, now that you've heard the rest of the candidates, maybe you're like, "Eh, I guess I can see why they went with NP-completeness." So circling back to what we now call the P
▶︎ 43:46 Versus NP question, again, the question of whether or not NP-complete problems are all efficiently solvable or whether none of them are, which of the worlds do we live in, the P not equal to NP world on the left or the P equal NP world on the right. So you ask around, you will get different opinions, but almost everyone's opinion of the experts, their money's on world number one. They would bet that, in fact, you cannot solve NP-complete problems in polynomial time.
▶︎ 44:18 There are exceptions. So one interesting counterpoint, all the way back in 1956, Gödel, yes, that same Gödel, wrote a letter to von Neumann, yes, that same von Neumann, conjecturing a statement equivalent to P equals NP. Now, mind you, 1956, so we're talking around here. So there hasn't even really been the definition of P yet. That came in the mid '60s. We're talking about the mid '50s. But Gödel basically said, "You know, I'll bet there's an algorithm that if you take a provable statement that has a short proof, I'll bet there's an algorithm that generates a short proof in not that much time, in time not that much more than what it would take to just write the proof down." And Gödel goes on to talk about the amazing consequences if that were in fact the case. So that's a conjecture that P equals NP. But again, that's the exception that proves the rule. Most people you ask will conjecture that we're actually in world number one.
▶︎ 45:21 So let's talk about why that is. Why is there so much, maybe confidence is the wrong word, but why is there so much consensus that the more likely outcome is that P is not equal to NP? So let me give you the first reason, which I think is probably the main reason which is driving most people's belief in P not equal to NP, which is, there's an asymmetry between how good we seem to be as a species coming up with algorithms versus coming up with proofs about the limitations of algorithms. So we're pretty good, honestly, at coming up with super clever algorithms that are much faster than what you might have expected would be possible. We saw one really obvious example in Karatsuba's algorithm for multiplication.
▶︎ 46:07 But then meanwhile, we have so many people that seem so good at coming up with algorithms, and then you've got people like Dantzig and Karp and Edmonds who have successfully solved so many different problems. All of them wind up getting stuck on, for example, the TSP, traveling salesperson problem. And with so many brilliant people thinking about it for so long, it kind of feels like if there were some fast algorithm to be found, wouldn't one of them have found it by now? And again, this may be a little egocentric, but you can imagine Edmonds saying, "You know, I thought about this a long time. This is, every other problem I was able to find an algorithm for, this one I can't. Maybe there isn't one."
▶︎ 46:49 And then from a similar place, actually, John Nash, believe it or not, the same Nash of the Nash equilibrium, if you're familiar with any game theory. So in the mid '50s, this is after he did his most famous game theory work, in the mid '50s he was actually getting obsessed with cryptography and cryptanalysis, and he was having secret communications with the NSA. And in one of those letters, when it was eventually declassified, he also conjectured something basically equivalent to P not equal to NP. He was basically conjecturing that the ciphers that he was coming up with were going to be unbreakable, or at least in a computationally feasible way, which, if true, would imply P not equal to NP. So again, that's the mid '50s, so that's way up in this timeline. And so Nash was already thinking about, again, he didn't have the language. He was thinking about a specific problem, not these whole collections of problems, but it's still the case that what was in Nash's letter, if true, would imply P not equal to NP.
▶︎ 47:48 And meanwhile, while we started this series with this terrific success in establishing limitations on computation in the form of Turing's theory of undecidability, to be honest, since Turing, successes have been few and far between as far as establishing fully satisfying proofs that computers can't do various tasks, especially, that they can't do various tasks efficiently. So if you imagine we are in world number one, so P is different to NP, it doesn't actually seem all that surprising that we just haven't figured out how to prove it yet, because again, as a species, at least thus far, we simply have not been very good at figuring out how to prove that there are things that algorithms can't do. The second reason, honestly, is just vibes.
▶︎ 48:36 It just seems to not be how the world works. It's kind of a law of nature. We know that if you take an expert-level Sudoku puzzle, we know that it's fundamentally harder to solve it from scratch than it is to just verify your friend's solution. Obviously, that first problem is harder than the second one. So it would seem that P not equal to NP is just, the only thing remaining is to verify that obvious intuition.
▶︎ 49:05 Now, honestly, neither of these reasons is really satisfying or convincing at all, really, if you sit down and think about it. P versus NP, that is a mathematical question. If P is not equal to NP, that is a mathematical statement when, if true, it has to have a proof. And as far as what that proof would look like, or even mathematical evidence of why we're so sure this would be true, there's actually shockingly little. And this may seem surprising. Why is it so hard to prove such a seemingly obvious statement?
▶︎ 49:37 But this is exactly where this kind of tension between what computers can and can't do, what algorithms can and can't do. So every time, if you're an algorithms person and you see an awesome algorithm like Karatsuba's multiplication, you're like, "That is amazing. That is a great victory for technology. We can solve this problem faster than we ever could before." If you're a lower bounds person who makes your career proving limitations on what algorithms could do, you freak out when you see Karatsuba's multiplication algorithm. You're like, "Seriously? Algorithms can do that? They can get speed ups for these inexplicable reasons?" How am I then supposed to prove that algorithms can't do some other crazy thing? How am I supposed to prove that algorithms can't magically find these shortcuts, even in NP-complete problems like the TSP, if they can be as wild as the shortcuts that we already saw in Karatsuba's algorithm?
▶︎ 50:28 And things have gotten to the point where, because everybody seems so stuck on trying to prove that P is not equal to NP, that theoretic computer scientists have now taken to trying to prove why it's hard to prove. So in some sense, using mathematics to justify their own failure in establishing that P and NP are different, establishing that we actually live in world number one. For example, if you were of the mind like, "Why is this so hard? This statement seems obvious. What would be some proof technique I could use to separate P from NP?" And a really good first thought would be like, "Well, what about diagonalization? It was good enough for Cantor in 1891. It was good enough for Gödel 40 years later. It was good enough for Turing five years after that. Why don't we just use diagonalization to separate P from NP, just like Turing used it to show that there are undecidable problems?"
▶︎ 51:24 And that's a good thought. But actually, really, not long after the theory of NP-completeness was developed, so in 1973, this is by Ted Baker, John Gill, and Robert Solovay, they proved something, again, back in the early '70s, something very striking. They showed that diagonalization, at least applied in the usual way, is fundamentally incapable of resolving the P versus NP question in either direction. So they proved there is no proof that's based on diagonalization in the usual way that could possibly resolve this question, that could possibly tell us which world that we're in.
▶︎ 52:04 Intuitively, what they show is that diagonalization would inadvertently prove a more general version of either P equal NP or P not equal to NP, and both of those general versions, you can show, are false. And so that's why diagonalization, again, at least used in a straightforward way, actually cannot succeed in resolving the question. So that kicked off a tradition which continues to survive, with theoretical computer scientists identifying, basically formally ruling out lots of different approaches you might take to trying to resolve this problem. So we know more than we used to in the sense that we know large swaths of our toolbox for proving impossibility results don't actually apply to the P versus NP question, a kind of certificate that any proof of this fact would have to be very novel indeed. So still, at the end of the day,
▶︎ 52:59 We wanna know who's right. Edmonds, who conjectured that P and NP are different, that there's no good algorithm for the TSP, or Gödel, who, in his letter to Von Neumann, conjectured that actually probably P and NP should collapse. You'd hope that, as the years go by, we'd be getting closer to a resolution of this fundamental question, one way or the other. But instead, as more and more of these mathematical approaches to the problem are now provably inadequate, honestly, the solution to the question seems to be receding further into the distance each year.
▶︎ 53:36 So we have to face the reality that, to learn the answer, we're gonna have to wait almost certainly years, and I would say probably decades. For a long time, actually, when I'd talk about this aspect of P versus NP, I would say, "And maybe even centuries," 'cause it just seemed so far out of reach. I have to say, speaking in 2026, what LLMs and generative AI have been able to do in mathematics over the past couple of years has made me a little bit more optimistic. So maybe I feel a little bit more comfortable with that timeline of decades than I used to. But we'll see.
▶︎ 54:14 Speaking of which, speaking of AI tools, you might ask, "Is all of this Turing, Cook, Levin, Karp stuff, is this even still relevant, given that generative AI and LLMs seem to be radically transforming technology and computation as we know it?" And then maybe you've also heard about other newfangled technologies, like quantum computing. You could ask the same question about that. So these actually are going to be exactly the topics that we take up in our next final episode of the series, right after we take care of our other outstanding order of business, namely the important ramifications of a proof of P equal NP, or alternatively, of a proof of P not equal to NP. So, I'll see you there.