In the last episode, we laid the difficult groundwork needed to seriously discuss the P versus NP question, which is what we will take up now. There were two big ideas introduced in that episode. The first was the identification of what intuitively counts as an easy problem with problems solvable by fast algorithms, and the identification of fast algorithms with polynomial-time algorithms. The P in P versus NP stands for polynomial, as in polynomial-time algorithm.
The right way to think about a polynomial-time algorithm is to ask: how does the problem size you can solve scale as your computer gets faster? Suppose you have a time budget of one minute. You buy a computer that is twice as fast, and the question is how much larger a problem you can now solve. 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 as your hardware improves. With a linear-time algorithm, for example, every doubling of computing power gives you a doubling of the problem size you can handle. With a quadratic-time algorithm, such as the grade-school method for multiplying two numbers, every doubling of computing power gives you roughly a 41% increase in the size of the problems you can solve. That is what we mean by a polynomial-time algorithm, and easy problems, or problems in P, are those solvable by a fast algorithm in this sense.
The second major concept introduced in the last episode was that of an NP-complete problem, which we are identifying with seemingly hard problems. An NP-complete problem is one where, on the one hand, it is very easy to check whether a proposed solution is correct. Think about Sudoku: it may be hard to construct a solution from scratch, but if someone else does the work and hands you the result, it is very easy to verify that it is indeed a valid solution. That is what we mean by an NP problem, a problem where it is easy to check a solution if one is handed to you. The NP-complete problems are specifically the hardest problems within NP; they are as hard as any other problem for which solution correctness is easy to verify.
At the end of the last episode, we recalled what it means to say one problem is as hard as another, the same meaning it carried back when we discussed 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, and in that sense problem B is at least as hard as problem A, because solving it allows you to solve problem A as well. A crucial consequence is that all NP-complete problems share the same computational fate: either all of them can be solved by efficient algorithms, or none of them can. They are all, in a precise sense, thinly disguised versions of the same problem.
There are only two possible worlds we could live in: one in which all the NP-complete problems are in P and are efficiently solvable, and one in which P and NP are different and none of the NP-complete problems are efficiently solvable. These two possibilities map directly onto what I would call the two big, complementary themes that run through this entire series. The first theme is what computers can do, and here, with P, we scale that down to ask what computers can do efficiently. The second theme is what computers cannot do, and again, in this context, we ask specifically what they cannot do efficiently.
These twin concerns, the power of computation and the limitations of computation, have been present since the very beginning. Both themes are already there in Turing's 1936 paper: the introduction of Turing machines to express what computers can do, and the undecidability arguments to express what they cannot. The two themes have a symbiotic relationship; work on what computers can do informs our understanding of what they cannot do, and vice versa.
What makes the P versus NP problem so remarkable is that it sits precisely at the intersection of these two themes, and we find ourselves stuck on both fronts simultaneously. If P equals NP, then there exist fast algorithms we have not yet discovered, meaning we need a deeper understanding of what computers can do efficiently. If P is different from NP, then there are ways of establishing limitations on algorithms that we have not yet found, meaning we need a deeper understanding of what computers cannot do efficiently. Progress on one of these two themes will ultimately resolve the question; we simply do not yet know which one.
Before we go deep on the P versus NP question, let me take some time to talk through the backstory and some of the history leading up to it. The short version, which I'll elaborate on, is that in the mid-twentieth century, the 1940s, 1950s, and 1960s, two distinct lines of research developed largely independently: 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. These two lines were pursued 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.
I find this history genuinely fascinating. You have this parallel evolution, people thinking about what computation can achieve and people thinking about what it cannot, and at some point they realize they are stuck at exactly the same place: the P versus NP question. Since Turing's paper, now literally ninety years ago, a majority of theoretical computer scientists have tended to specialize in one of these two themes, either understanding the power of algorithms or focusing on their limitations.
Researchers in the first camp, who think about what algorithms can do, focus on what they call possibility results or upper bounds, and they typically self-identify as algorithms researchers. There is a historically distinct group of theoretical computer scientists who focus on the limitations of computation, on impossibility and negative results, and those researchers tend to self-identify as complexity theorists or lower bounds researchers, since their work centers on proving the inherent difficulty of computational problems.
This dichotomy is obviously an oversimplification. Many theoretical computer scientists, especially the most celebrated ones, defy easy categorization and make contributions to both themes. Nevertheless, it remains a useful sociological grouping of researchers in this area, and it is worth keeping in mind as we trace how these two traditions eventually converged.
From a distance, mathematics probably seems, more than most disciplines, like a logically unified field. There are basic axioms that nearly everyone agrees upon, and the entire enterprise consists of exploring the consequences of those axioms. In practice, however, mathematical researchers tend to cluster into groups defined by the methodology they use. As fields mature and advances require deeper specialization, this fragmentation becomes more and more pronounced, producing distinct sub-communities bound together by a common toolbox for making progress.
The toolbox for proving limitations on computation, for establishing impossibility results and lower bounds, is historically rooted in logic. Recall from the first episode that Gödel's incompleteness theorem was an important precursor to Turing's work on undecidability, and that tradition still exerts influence today. As a result, researchers drawn toward proving impossibility results tend, broadly speaking, to have a pure mathematics mindset: a theory-building orientation rather than a problem-solving one.
The other side of the coin is possibility results, algorithms and upper bounds. As we saw with Karatsuba's remarkable multiplication algorithm, there is brilliant work to be done in uncovering unexpected things that computers can do. Contributions of that kind typically require deep insight into the specific structure of a problem: locating redundant work hidden inside a straightforward solution, and then exposing that redundancy so it can be reused rather than recomputed. For this reason, researchers in algorithms tend to have more of an engineering mindset, a problem-solving orientation rather than a theory-building one.
With that distinction in hand, we can revisit the cast of characters encountered so far and ask a natural question: which of the computer scientists and mathematicians we have discussed fall into the algorithms and upper-bounds camp, which fall into the impossibility-results and lower-bounds camp, and which do not fit neatly into either category?
Let's classify our cast of characters as either algorithms researchers, if they focused on what computers can do, or lower bounds researchers, if they were more interested in the limitations of computation. I'll proceed roughly chronologically according to the contributions we discussed.
Our starting point was 1936 and Alan Turing, who is definitely one of the hardest researchers to classify. I encourage you to read more about him if you have the time; he is a fascinating figure. For the purposes of this series, because we are zooming in specifically on his development of the theory of undecidability, I'll classify Turing as a lower bounds researcher, though with an asterisk. By all accounts, Turing had something of an engineer's mindset, constantly tinkering with machines and physical experiments, very much a generalist. But for our story, he belongs primarily in the lower bounds camp. We also discussed Church at roughly the same time, but he was really a pure logician, so I'll leave him off the list.
We mentioned Von Neumann several times, for example, in the late 1940s working on projects like the EDVAC and the ENIAC to realize general-purpose computers. He is again very difficult to classify, possessing remarkable results in pure mathematics. For our story, however, his contributions center on building computers and making them work, which reflects an engineering mindset, so I'll place him in the algorithms camp, also with an asterisk. Notably, as far back as 1945, when people were just beginning to dream about computers rather than actually building them, Von Neumann invented the celebrated algorithm mergesort, which is lecture two in any algorithms course, before the machines he was working on had even been completed.
Another figure from the late 1940s is George Dantzig, famous for the simplex method and also for the story of arriving late to class, seeing two problems on the board, and solving them thinking they were homework. Dantzig is a clear example of an algorithms researcher: he genuinely wanted to help people solve problems that mattered for the military and for business. Into the 1950s he was thinking hard about the traveling salesman problem as well. A straightforward algorithms classification, no asterisk needed.
We also discussed Edsger Dijkstra, who made contributions across all of computer science, perhaps best known for his effort to turn programming into more of a science than an art, using logical methods to write programs that could be formally proved correct. For our purposes, he belongs in the algorithms camp for his invention of Dijkstra's algorithm for computing shortest paths, though again an asterisk is warranted given the extraordinary breadth of his work.
The other algorithm we examined in the second episode was Karatsuba's method for integer multiplication, which arose out of a research seminar run by Andrei Kolmogorov around 1960. By that point, computers were being built and seriously used, and Kolmogorov was one of the first major mathematicians to take seriously the mathematics of optimal computation. His focus was largely on the lower bounds side: his conjecture, the one that catalyzed Karatsuba, was that you could not beat the straightforward quadratic-time algorithm we all learned in school. Karatsuba, of course, demolished that conjecture by producing a faster algorithm. Karatsuba himself I won't place on this list; he was really a pure mathematician, primarily a number theorist, and his integer multiplication result appears to have been something of a side quest that emerged from attending Kolmogorov's seminar. Kolmogorov, who ran that seminar, belongs firmly in the lower bounds camp.
We also mentioned Alan Cobham, one of at least two people who independently proposed identifying efficient computation with computations requiring only a polynomial number of steps: the idea that the right criterion for efficiency is that doubling your computing power yields a percentage increase in the problem size you can handle. Not much is known about Cobham, and his publication record is sparse, but based on what I know, my best guess is that he was primarily a lower bounds researcher.
The other person who arrived at the notion of polynomial time around the same time was Jack Edmonds, who was very much an algorithms person. Edmonds produced some of the most beautiful algorithms in combinatorics that we still use today, particularly around matching problems: situations where you have a collection of objects or people and want to pair them up in an optimal way. When Edmonds got stuck on the traveling salesman problem, he conjectured that no polynomial-time algorithm for it existed, but his orientation was always that of an algorithms researcher.
Finally, we concluded with the Cook–Levin theorem. Stephen Cook, at Berkeley and later Toronto, is very much a lower bounds person, rooted in the traditions of logic and of Turing, and more interested in the general theory of NP-completeness than in specific algorithms for specific problems. Leonid Levin, who was doing his work behind the Iron Curtain, earned his first PhD from Moscow State University, the very institution where Kolmogorov had run the seminar that Karatsuba attended, and his advisor was Kolmogorov himself. Levin essentially inherited the lower bounds mindset from Kolmogorov, which is fitting given that his work came roughly a decade after Karatsuba's. He later earned a second PhD at MIT after coming to the United States. Both Cook and Levin belong squarely in the lower bounds camp.
Some colleagues might quibble with a few of these classifications, but going back through the full cast of characters we have encountered thus far, that is how I would place them.
Why bring up all this history? Partly because it's genuinely interesting (we've already encountered many famous names in mathematics and computer science), but the main reason is to provide the historical backdrop for the articulation of the P versus NP question. On one side, you had researchers focused on algorithms, figuring out ways for computers to solve particular problems faster and faster, working largely with an engineering mindset. On the other side, researchers coming from pure mathematics were focused on lower bounds, trying to establish limits on what algorithms could possibly achieve. Through the 1940s, 1950s, and 1960s, these two threads of research evolved largely independently, pursued by largely different groups of people. There were points of contact: Cobham and Edmonds, for instance, independently arrived at the same concept of polynomial-time computation as the right way to express efficient computation. But the two communities were mostly distinct.
Now let me add one more name to the list, a name mentioned briefly in the last episode without a full account of his contributions: Richard Karp. Karp was very much an algorithms person, responsible for a number of breakthrough algorithms in the 1960s, 1970s, and 1980s, and he spent most of his career at Berkeley, where he is now a professor emeritus. He has, for example, an early paper on the maximum flow problem co-authored with Edmonds from the early 1960s, a paper whose content I still teach today. The point is that at the time NP-completeness emerged, Karp was a deeply seasoned, in-the-trenches algorithms researcher.
From Karp's vantage point at Berkeley, Levin's work was not yet accessible; it would not reach North America for well over a decade. Cook, however, was at Toronto and published his version of the Cook-Levin theorem in 1971. By that time Karp was around forty years old and had spent well over a decade trying to devise fast algorithms for a wide range of problems. Many he had solved, and I still teach many of those algorithms today. Some he had not. Like Dantzig before him, Karp became somewhat obsessed with the traveling salesman problem. He did manage to improve on exhaustive search by identifying redundant computations that could be isolated and reused, but a polynomial-time algorithm remained out of reach despite enormous effort. And he knew, off the top of his head, many other problems that looked tantalizingly similar to problems he could solve efficiently, yet for which neither he nor anyone he knew could find a fast solution.
When Cook's paper appeared in 1971, Karp read it almost immediately after publication. What would come to be called the theory of NP-completeness (the name didn't yet exist, but we'll get to that) Karp instantly recognized as a once-in-a-generation unlock that simultaneously explained the barriers being encountered by researchers across the entire algorithms community, himself included. For the first time, he had a principled explanation: it wasn't that he was simply failing to be clever enough on a given day. Cook's new theory was the explanation for why he and all of his colleagues were stuck precisely where they were stuck.
Cook's paper itself established the NP-completeness of two natural problems: satisfiability, a problem in logic, and subgraph isomorphism, a problem about networks. One can imagine that to a complexity theorist like Cook, the main theoretical work was done. The framework had been built, and it was for others to apply it to specific problems. Karp, as an algorithms researcher, was more than happy to take the torch from that point. He took Cook's theory and the two initial examples, and through a systematic program of reductions, spread the idea of NP-completeness to many, many other problems, including all of the ones he had been trying to solve for the previous fifteen years without success.
By all accounts, this was an extraordinarily exciting period in Karp's career, and he has written about it himself. For the remainder of 1971 and much of 1972, he was essentially full-time bouncing ideas off anyone willing to engage, constantly constructing new reductions between pairs of problems and establishing more and more problems as NP-complete beyond Cook's originals. There were informal meetups in the San Francisco Bay Area where the theoretical computer science community would gather, and Karp would try out the reductions he was developing. The culmination came at a symposium held at the IBM research laboratory in Yorktown Heights, New York, which still operates today, where Karp unveiled a list of 21 NP-complete problems. Cook had established two; Karp had expanded the list to twenty-one. Among those twenty-one, very satisfyingly for him, was the traveling salesman problem.
Karp did show that TSP is NP-complete. If NP-complete problems do not have fast algorithms, then that explains why Dantzig, Edmonds, Karp, and others had failed to find a fast algorithm for TSP up to that point. That was really the big bang for NP-completeness. Experts were certainly aware of Cook's paper, but Karp took what was essentially a lower-bounds paper and showed that it also explained everything going on for algorithms researchers.
All of a sudden, even researchers who had never read a paper on the limits of computation wanted to know about NP-completeness, both to justify their failures on problems they had already struggled with and to avoid wasting time on other problems that turn out to be NP-complete and for which no fast solution should be expected. With Karp's demonstration, it became clear to everyone that NP-completeness would revolutionize our understanding of efficient algorithms and their limitations.
Moreover, while the theory by itself does not resolve whether NP-complete problems are efficiently solvable, it takes what would seem to be many different open questions, such as the 21 problems on Karp's list, each asking independently whether that problem admits an efficient algorithm, and reduces them to a single open problem. NP-complete problems all share the same computational fate: either all 21 of Karp's problems are efficiently solvable, or none of them are.
Before returning to the whiteboard to revisit the pictures of the two different worlds discussed in the previous episode, a brief personal note: one of the rewarding aspects of working in a relatively young field like computer science is that, if you are fortunate, you will have the opportunity to meet some of the early researchers who shaped how the field has evolved.
I've been tremendously lucky in that regard. I've met all three of Cook, Karp, and Levin, all of whom are still alive. There is a major annual theoretical computer science conference called STOC (spelled S-T-O-C), and the 2021 edition marked the 50th anniversary of the Cook-Levin theorem. It was Stefano Leonardi's idea to assemble a special anniversary session devoted to that theorem, and I had the privilege of serving as moderator while Cook, Levin, and Karp all participated.
It was remarkable to hear all three of them recount what life was like during that period. Particularly striking was Levin's account of working largely in isolation in the Soviet Union, unaware of the work that Cook and Karp were doing on the other side of the Iron Curtain. The session is easy to find on YouTube, and I encourage you to check it out.
Let me remind you how to visualize this now-unified open question: whether all NP-complete problems are efficiently solvable, or whether none of them are. We are in one of only two worlds. That is the power of NP-completeness and the universality of NP-complete problems. There are only two possibilities, they are very different from one another, and we do not know which one we inhabit, which is frustrating and maddening. The world either looks like the picture on the left or the picture on the right.
To recall: the picture on the left represents the world as Edmonds envisioned it when he conjectured that there is no polynomial-time algorithm for the Traveling Salesman Problem. The large region represents all of NP, all problems for which a solution can be recognized easily if someone shows you one. The smaller region at the bottom, P, is a subset of NP and contains the easiest problems in it. Problems like computing shortest paths, for which we have Dijkstra's algorithm, belong down in this polynomial-time-solvable region.
According to Edmonds' conjecture, the TSP, while still belonging to NP (if someone shows you a tour of an amusement park that takes only thirty minutes, that is straightforward to verify), lies outside the easy part of NP and is not efficiently solvable. With the Cook-Levin theory, we now have the notion of NP-complete problems: a special class of NP problems that are not only efficiently verifiable, but are in fact universal, encoding every problem in NP. Every problem for which solutions can be efficiently recognized is in effect a special case of an NP-complete problem, and as Karp established, the TSP is one of them.
On the other hand, if anyone ever finds a polynomial-time algorithm for even one NP-complete problem, everything collapses. All NP-complete problems share the same fate. Pull one into the easy region, and all of them follow, and we find ourselves in World Number Two: a world where there are generic algorithmic shortcuts for all problems whose solutions are easy to recognize. Whenever you can recognize a solution, you can also find one far more quickly than exhaustive search would suggest. The P versus NP question is, at its core, simply this: do we live in World Number One, or do we live in World Number Two?
The P versus NP question is simply a choice between World Number One and World Number Two. World Number One corresponds to the case where P ≠ NP, meaning that P and the NP-complete problems do not overlap. World Number Two is where everything collapses and P = NP.
Conceptually, the question asks whether an algorithmic shortcut, like the one exploited by Dijkstra's algorithm for shortest paths, is somehow very problem-specific, or whether such shortcuts are ubiquitous, shared by literally every computational problem for which you can recognize a solution when you see one. That condition does not cover every problem in existence: the halting problem, for instance, is not an NP problem. But it does cover nearly all of the problems we encounter in everyday life, where valid solutions are indeed easy to verify.
The P versus NP question is therefore one of the most important open questions in all of science. There are vast numbers of NP-complete problems, including many we would dearly love to solve efficiently. Either all of them are tractable, or none of them are, and we simply do not know which world we inhabit. The question remains open, and either outcome is mathematically possible. Most researchers believe we live in World Number One, that P is genuinely different from NP, but this has never been mathematically established.
This is an extremely important problem, and it is now widely recognized as such. Back in the first episode, when we were filling in the backstory for Turing's work, we discussed David Hilbert and how, at the 1900 International Congress of Mathematicians in Paris, Hilbert used his keynote lecture to propose 23 open mathematical problems he thought people should work on, one of them being the problem that Turing resolved in the negative in his 1936 paper.
A hundred years later, in 2000, the Clay Mathematics Institute issued what they called the Millennium Problems: a list of seven open mathematical problems, all of which were unsolved at the time. Since then, one of the seven has been solved; the other six remain open. The P versus NP question was, rightfully, included among those seven. You may have heard of some of the others: the Riemann hypothesis, the Navier–Stokes equations, and the one that has since been solved, the Poincaré conjecture. At this point, P versus NP is mainstream opinion as one of the deepest and most important open questions in all of mathematics.
If you want to know more about the Millennium Prizes, the 25th anniversary of those problems was last year (I am speaking now in 2026), and the Clay Mathematics Institute recently posted a series of videos by prominent computer scientists and mathematicians giving updates on each of the seven questions. For P versus NP in particular, there is a lecture by Avi Wigderson, the legendary theoretical computer scientist, discussing the current state of the art on that problem.
What happens if you solve one of these Millennium Prize problems? Fame and fortune, fame certainly. The prize money is one million dollars, which in some ways is a great deal, but given how important these problems are and what an extraordinary achievement resolving any one of them would represent, one million now seems far too low. If any billionaires listening to this are looking for a philanthropic cause, you might consider supplementing the Clay Mathematics Institute's prize fund, perhaps bringing each prize to ten times its current value, including the one for P versus NP.
As mentioned, one of the problems has been resolved: the Poincaré conjecture. And, as I noted in the first episode, it is almost too easy to find stories of eccentric behavior among mathematicians. Remarkably, the person who solved the Poincaré conjecture refused to collect the one-million-dollar prize from the Clay Mathematics Institute, meaning, as far as anyone knows, all seven million dollars remains in the bank. With that, I turn to the stories I promised earlier about the alphabet soup surrounding the P versus NP conjecture.
After Karp popularized Cook's work, and remember, Karp was unaware of Levin's work at the time, so he was building solely on Cook's results, he greatly expanded its scope by demonstrating that NP-complete problems were not just a handful of isolated examples. There were going to be a great many of them. Once Karp made that clear, everyone wanted to know the answer to the central question: are there fast algorithms for all of Karp's problems, or are there no fast algorithms for any of them? It became clear that this was going to be a fundamental question in theoretical computer science, and so everyone agreed that good terminology was needed to discuss it.
In his 1971 paper, Cook had discussed the concepts of P, problems solvable by polynomial-time algorithms, and NP, problems with efficiently checkable solutions, without actually introducing concise names for either concept. It was Karp, in the paper accompanying his list of 21 problems, who introduced the terminology P and NP, and those names have stuck ever since. P stands for polynomial, because these are problems that can be solved by a polynomial-time algorithm.
As for NP, and there is a reason it was not mentioned earlier, people tend to be curious about what it stands for until they hear the answer, at which point they rather wish they had not asked. The most important thing to understand about NP is what it does not stand for. The classic rookie mistake is to assume it stands for "not polynomial," that P and NP simply mean "polynomial" and "not polynomial." That is incorrect. If you must know, NP stands for "non-deterministic polynomial." Non-determinism, the idea that an algorithm might behave differently on the same input across multiple runs, turns out to be an equivalent way of expressing the idea of efficiently checkable solutions. That equivalence is the deeper reason for the name, even if the phrase itself feels somewhat anachronistic today.
The modern way to think about NP problems is simply this: you know a valid solution when you see one. With P and NP accounted for, the remaining term is NP-complete, which, viewed from the outside, can feel like a hopelessly inscrutable label. It does not immediately convey much content from its phrasing alone, and that is a genuine disservice to the fundamental concept it defines, a concept that deserves widespread appreciation, and even a sense of wonder. We have already discussed how remarkable it is that NP-complete problems exist at all: the idea that a single problem can serve as a universal proxy for an entire class of problems is extraordinary.
Mathematically, the convention is to call a problem X-complete, for some class X, if the problem is both a member of X and is at least as hard as every other problem in X, where "at least as hard" is made precise using the notion of a reduction. That, in essence, is what NP-complete means.
Believe it or not, some thought was put into what this concept should be called. Cook himself did not give it a name, and Levin was not part of the conversation, since he was in the Soviet Union. Don Knuth, without doubt one of the most famous computer scientists of all time, known for The Art of Computer Programming among many other things, immediately recognized how important the theory Cook had developed was going to be. Like Karp, Knuth would belong primarily in the algorithms camp, but he had shaped a great deal of computer science from the 1950s onward, and he had given names to many things along the way.
Knuth understood that a science can be more successful when its concepts are named attractively. So he effectively crowd-sourced suggestions. This was 1974, so posting on Twitter was not an option, but there was a newsletter that all theoretical computer scientists read called SIGACT News, and Knuth put out a call asking what we should name what we now call NP-complete problems.
The broader scientific community answered, and the suggestions were illuminating. Among the more serious proposals were Herculean, formidable, and arduous, all of which share the same subtle problem: they presuppose that P ≠ NP is the correct answer. Among the less serious write-ins, hard-boiled was submitted as a tribute to Steve Cook. And, in a suggestion that very much reflects the 1970s, Albert Meyer proposed hardass, allegedly standing for "as hard as satisfiability."
One particularly clever proposal came from researcher Shen Lin, who suggested PET, a pleasingly flexible acronym whose expansion could adapt to however the P versus NP question was eventually resolved. If P ≠ NP remained unproven, it could stand for probably exponential time. If P ≠ NP were actually proved, it could become provably exponential time. And in the unlikely event that P turned out to equal NP, it could be read as previously exponential time.
Having heard the full range of candidates, perhaps it becomes easier to see why NP-completeness was the name that stuck.
Circling back to what we now call the P versus NP question, the question of whether NP-complete problems are all efficiently solvable or whether none of them are: which of the two worlds do we live in, the P ≠ NP world or the P = NP world? If you ask around, you will get different opinions, but almost every expert would bet on world number one. They would wager that NP-complete problems cannot be solved in polynomial time.
There are exceptions worth noting. All the way back in 1956, Gödel (yes, that Gödel) wrote a letter to von Neumann (yes, that von Neumann) conjecturing a statement equivalent to P = NP. Bear in mind that this was around the mid-1950s, before the formal definition of P had even been established; that came in the mid-1960s. Gödel essentially argued that if a mathematical statement has a short proof, there should be an algorithm that generates that short proof in time not much greater than what it would take to simply write the proof down. He went on to describe the remarkable consequences if that were true. So Gödel's conjecture actually favored P = NP, but that is the exception that proves the rule. Most people conjecture that we live in world number one.
Why is there such consensus that P ≠ NP is the more likely outcome? The first reason, and probably the main one driving most people's belief, is a striking asymmetry between how capable we are as a species at devising algorithms versus proving limitations on algorithms. We are genuinely quite good at discovering clever algorithms that are far faster than one might have expected. Karatsuba's algorithm for integer multiplication is one vivid example. And yet, brilliant researchers like Dantzig, Karp, and Edmonds, who successfully solved so many difficult problems, all found themselves stuck on problems like the Traveling Salesman Problem. With so many talented people thinking about these problems for so long, it is hard to escape the feeling that if a fast algorithm existed, someone would have found it by now.
Along similar lines, John Nash, the same Nash of the Nash equilibrium, was, in the mid-1950s, after his most celebrated game-theory work, becoming deeply interested in cryptography and cryptanalysis, and was conducting secret correspondence with the NSA. In one of those letters, eventually declassified, he conjectured something essentially equivalent to P ≠ NP. He was arguing that the ciphers he was constructing would be computationally infeasible to break, which, if true, would imply P ≠ NP. Nash did not yet have the language of complexity classes, and he was focused on a specific problem rather than entire families of problems, but the substance of what he wrote would, if correct, imply P ≠ NP.
Meanwhile, although this series began with the tremendous success of establishing limitations on computation through Turing's theory of undecidability, successes of that kind have been few and far between ever since. We have simply not been very good, as a species, at proving that algorithms cannot accomplish various tasks efficiently. If we are indeed in world number one, if P ≠ NP, it is not at all surprising that we have not yet managed to prove it, given how poorly equipped we have historically been at proving such lower bounds. The second reason, honestly, is just a matter of intuition and collective instinct.
It just seems to not be how the world works: it feels like a law of nature. We know that an expert-level Sudoku puzzle is fundamentally harder to solve from scratch than it is to simply verify a friend's solution. Obviously, the first problem is harder than the second. It would seem, then, that P ≠ NP is simply true, and that all that remains is to confirm that obvious intuition.
Neither of these reasons is truly satisfying or convincing, however, if you sit down and think carefully. P versus NP is a mathematical question, and if P ≠ NP is true, it is a mathematical statement that must have a proof. Yet as for what that proof would look like, or even what mathematical evidence exists to justify our confidence, there is actually shockingly little. This may seem surprising: why is it so hard to prove such a seemingly obvious statement?
There is a fundamental tension between what computers can and cannot do, between what algorithms can and cannot accomplish. Every time an algorithms researcher encounters something like Karatsuba's multiplication algorithm, the reaction is one of genuine excitement: "That is amazing. That is a great victory for technology. We can solve this problem faster than we ever could before." But for someone who makes their career proving lower bounds, formal limitations on what algorithms can do, Karatsuba's algorithm is deeply unsettling. If algorithms can achieve speedups for such inexplicable reasons, how is one supposed to prove that algorithms cannot do some other equally surprising thing? How can we prove that algorithms cannot magically find shortcuts even in NP-complete problems like the Travelling Salesman Problem, when the shortcuts we have already witnessed are as wild as those in Karatsuba's algorithm?
Things have reached the point where, because everyone seems so stuck on trying to prove that P ≠ NP, theoretical computer scientists have turned to proving why that proof is hard to find, using mathematics, in some sense, to explain their own failure to establish that P and NP are different. A natural first thought for anyone wondering why this is so difficult might be: "What proof technique could separate P from NP?" A compelling candidate is diagonalization. It was good enough for Cantor in 1891, good enough for Gödel forty years later, and good enough for Turing five years after that. Why not simply use diagonalization to separate P from NP, just as Turing used it to show that undecidable problems exist?
That is a reasonable thought, but not long after the theory of NP-completeness was developed, it was decisively ruled out. In 1973, Ted Baker, John Gill, and Robert Solovay proved something very striking: diagonalization, at least applied in the usual way, is fundamentally incapable of resolving the P versus NP question in either direction. Intuitively, what they showed is that a diagonalization argument would inadvertently prove a more general version of either P = NP or P ≠ NP, and both of those more general statements can be shown to be false. That is precisely why diagonalization, used in any straightforward manner, cannot succeed in resolving the question.
This result kicked off a tradition that continues to this day, with theoretical computer scientists formally ruling out large classes of approaches one might take toward resolving the problem. We know more than we once did, in the sense that we have identified broad swaths of our impossibility-proving toolkit that simply do not apply to the P versus NP question. This constitutes a kind of certificate that any eventual proof of this fact would have to be genuinely novel, unlike anything that has come before.
At the end of the day, we want to know who is right: Edmonds, who conjectured that P and NP are different and that there is no efficient algorithm for the TSP, or Gödel, who in his letter to Von Neumann conjectured that P and NP should probably collapse. One would hope that, as the years go by, we would be getting closer to a resolution of this fundamental question, one way or the other. Instead, as more and more mathematical approaches to the problem are now provably inadequate, the solution seems to be receding further into the distance each year.
We have to face the reality that learning the answer will almost certainly require years, and most likely decades. For a long time, when discussing this aspect of P versus NP, I would add "and maybe even centuries," because a resolution seemed so far out of reach. Speaking in 2026, however, what LLMs and generative AI have accomplished in mathematics over the past couple of years has made me somewhat more optimistic, and I feel a little more comfortable with a timeline of decades than I once did. But we shall see.
This raises a natural question: is all of this work by Turing, Cook, Levin, and Karp even still relevant, given that generative AI and LLMs seem to be radically transforming technology and computation as we know it? One might ask the same question about other emerging technologies, such as quantum computing. These will be exactly the topics taken up in the next and final episode of the series, right after we address our remaining order of business: the important ramifications of a proof of P = NP, or alternatively, of a proof of P ≠ NP.