Let me remind you where we left off in the last episode. We were talking about how the map application on your phone computes driving directions, and that led us to discuss Dijkstra's algorithm, an efficient method for computing a shortest path from one point to another. Along the way, we observed that what makes this remarkable is the potentially astronomical number of options for what the shortest path between two points could be. Dijkstra's algorithm cleverly sifts through that enormous number of candidate solutions to very quickly hone in on the right answer.
To remind you why the number of routes can blow up exponentially as a network grows, recall the example we looked at previously. We were thinking about traveling from point A to point B, imagining four independent decisions to make: at each stage, you can take the northern route or the southern route. With the travel times we assigned, it is not hard to see that the optimal strategy is to alternate between the northern and southern routes. That was not a difficult problem; we did not have to think hard to figure out the right answer.
What we did observe, however, is that we were doing something clever: we were using a shortcut. Rather than performing an exhaustive search, enumerating all two times two times two times two, or 16, different routes and comparing them individually, we simply asked what the best choice is at each stage. In a more complex network, like the ones we navigate every day, it is far less obvious how to identify such a shortcut, but that is precisely what Dijkstra's algorithm accomplishes.
We also noted that without something like Dijkstra's algorithm, without a way to exploit this algorithmic shortcut and sift through all the options, computing the shortest path from point A to point B in a reasonably large network would be completely infeasible. If you chain just 265 of these binary-choice stages in a row, the number of options is roughly on the order of the estimated number of atoms in the known universe. And 265 stages is not unreasonable for a multi-state driving trip. The takeaway is clear: shortest path problems involve an enormous number of options, yet we do not need to examine them all. We very quickly hone in on the best one.
Can we always find such algorithmic shortcuts? We already know, from the halting problem, that some problems have no algorithm at all. But setting that aside, for the kinds of problems we encounter in everyday life, is it possible that algorithmic shortcuts always exist, or are we sometimes genuinely forced to examine every possible option?
We discussed John von Neumann earlier in this series, back when we were covering the first serious attempts to realize general-purpose computing devices. Von Neumann was a remarkably quotable person. One of his quotes, which I don't entirely agree with, though there is a grain of truth to it, is: "In mathematics, you don't understand things. You just get used to them." I do think you feel your understanding deepening as you study more and more mathematics, but there is always some material where you find yourself thinking, "Well, that's just how it works," and you simply get used to it.
For people who think seriously about computation and algorithms, one of those things you have to get used to is that seemingly minor modifications to a problem statement, very small changes in the computational task you are trying to carry out, can have a dramatic effect on how quickly the problem can be solved.
Consider the shortest path problem with a small but significant modification: instead of finding the shortest path from point A to point B, we also require visiting every other intersection along the way. Imagine a larger network with 100 intersections, and the goal is to travel from point A to point B while passing through all 100 other locations en route. A familiar real-world analogy is taking your children to an amusement park where they insist on riding every ride exactly once. You must visit every attraction and do so as efficiently as possible.
This is a famous variant of the shortest path problem known as the Traveling Salesman Problem, or the TSP. It is a problem that, even during the golden age of algorithms in the 1940s, '50s, and '60s, when researchers like George Dantzig were successfully tackling a vast range of difficult problems, stubbornly resisted every attempt to find an efficient solution, despite the brightest minds of the era working hard on it.
The TSP shares several features with the shortest path problem. In principle, it can be solved through exhaustive search: starting at point A, one can enumerate every possible sequence of stops until reaching destination B, then select the shortest. For a tiny network, this brute-force approach is perfectly correct. However, just as with shortest paths, the number of possibilities grows exponentially as the number of locations increases, making exhaustive search completely infeasible for networks of even a few hundred locations. The computation would not complete within any human lifetime.
The natural hope would be that the TSP also admits an algorithmic shortcut analogous to Dijkstra's algorithm for shortest paths. Despite the surface similarity between the two problems, and despite the existence of such a powerful shortcut for shortest paths, no one has yet discovered an efficient algorithmic shortcut for the TSP. As of 2026, the problem remains unsolved in this sense.
This difficulty is not for lack of trying. Many brilliant minds have thought very hard about finding fast algorithms for the Traveling Salesperson Problem. They have made some progress: it is actually known how to do a bit better than exhaustive search. Just as in our multiplication example, one can expose redundant work and reuse computations rather than recomputing them from scratch, yielding some degree of optimization. But even after all of those ideas have been exhausted, one is still left with algorithms that are unable to solve more than very small instances in a reasonable amount of time.
After so many brilliant people thinking for so long without producing a fast algorithm for TSP, one has to start wondering whether, despite its superficial similarity to shortest paths, the Traveling Salesperson Problem is simply a problem of a fundamentally different nature, one that truly eludes efficient computation.
As a sanity check, though, we should not go overboard. TSP is definitely not one of those undecidable problems, like the halting problem, which cannot be solved by computer at all. No algorithm, running for any amount of time, is guaranteed to solve the halting problem. TSP is a gentler beast: there is certainly a finite algorithm for solving it, because one could enumerate all possibilities, and there are only finitely many, and simply remember the best. So if TSP is a hard problem, it is hard in a scaled-down sense compared to the undecidable problems that Turing identified.
All of this puts us in an uneasy state of ignorance. On the one hand, we do not know how to solve TSP efficiently; we have no fast algorithm analogous to Dijkstra's algorithm for the shortest path problem. On the other hand, we do not know how to argue that no fast algorithm exists, the way we can argue that no algorithm of any kind solves the halting problem. We have neither an analog of Dijkstra's algorithm nor an analog of Turing's undecidability argument, and so we are left not knowing whether TSP is efficiently solvable or not.
In the 1950s and 1960s, many brilliant algorithms researchers were thinking hard about problems like the Traveling Salesperson Problem, and after trying long and hard without success, there was a temptation to conjecture that if they couldn't find an algorithm, probably no algorithm existed. Jack Edmonds, a legend in algorithm design whom we'll discuss more later, thought deeply about the TSP throughout the 1960s. In 1967, he wrote in one of his papers, "I conjecture that there is no good algorithm for the Traveling Salesperson Problem." We'll return shortly to what he meant by a good algorithm.
Edmonds then added something rather amusing: "My reasons are the same as for any mathematical conjecture. First, it is a legitimate mathematical possibility, and second, I do not know." If those are truly the only two criteria required, one might just as well conjecture the opposite, that the TSP does have a good algorithm. In any case, that was Edmonds's conjecture of 1967, and as we'll see, the claim that the TSP is unsolvable by efficient algorithms turns out to be equivalent to the famous conjecture that P ≠ NP. It was one of the earliest known equivalent formulations of that problem.
In the next episode, Episode 4, we'll take a deep dive into the P versus NP question, covering the historical backdrop of how researchers came to identify it as the central open problem in the field, and then exploring the ramifications of what it would mean if P = NP or if P ≠ NP. The goal of this episode, Episode 3, is more focused: to introduce the two main protagonists in that question. On one side, we have the class of problems that are efficiently solvable, those for which a fast, automated procedure exists. On the other side, we have problems like the TSP that appear to be fundamentally resistant to efficient algorithms, and these are known as the NP-complete problems.
Those are the two key goals of this episode. What is a polynomial-time solvable problem? That concept corresponds to the P in P versus NP. And what are the NP-complete, or seemingly intractable, problems? That is part of the story on the NP side of the question. With that framing in place, let's get into it, beginning with P.
What does P stand for? Hold that thought; we will return to it shortly. The idea is that P should capture problems that are, in some sense, easy. What does easy mean? It means they should be solvable by a fast algorithm. Think of this as a refinement of Turing's notion of decidability from his 1936 paper. Turing was interested in problems that can be solved, at least in principle, by a computer. Now we are zooming in on problems that can be solved quickly by a computer.
If an easy problem is one solved by a fast algorithm, the question becomes: what do we mean by a fast algorithm? Intuitively, we want to say something like: if an algorithm can handle problem instances of a reasonably large size in an hour or less on a laptop, that should count as fast. If it would take a year to finish on that same laptop, that should not count as fast.
We have already seen some algorithms that we would intuitively classify as fast. Take multiplying two numbers: forget about Karatsuba, even the grade-school method feels like a fast algorithm. If you had numbers with thousands of digits, that would be tedious to do by hand, but those thousand partial products are completely trivial for a modern computer. Tens of thousands of digits? No problem. With Karatsuba's method, it would be even faster.
The same applies to Dijkstra's algorithm. The idea is that you explore, in parallel, all paths radiating out from the origin until you reach the destination, and the amount of work involved scales well to very large networks. Thousands of intersections and roads? No problem. Tens of thousands of intersections and roads? Still no problem, and even on a modern laptop, Dijkstra's algorithm completes very quickly. These are fast algorithms: they handle problem sizes that would be, at best, annoying and, at worst, impossible to do by hand, and they finish in under a second.
Exhaustive search, by contrast, intuitively should not be a fast algorithm. Even for fairly small networks, enumerating all possible routes might take a year. For medium-sized networks, you are talking about billions of years to complete. That, intuitively, is the difference between a fast algorithm and a slow one.
At this point, you might be thinking: the P versus NP question is supposed to be a mathematical problem, so there must be an actual mathematical definition of what makes a problem easy, or what makes an algorithm fast. You are right, there is. That definition is coming next. You may be sorry you asked, but I will give you the precise mathematical formulation.
We are going to identify fast algorithms with what are known as polynomial-time algorithms. The P in that term stands for polynomial. A polynomial is a simple function of one input, expressions such as x² + 3x + 2, or x10 − 9x7 + 3. You plug in a number, apply a simple formula, and get an output number. Those are examples of polynomials.
This notion of polynomial time is also exactly what Edmonds had in mind when he conjectured that there is no good algorithm for the TSP. Around the same time, Alan Cobham, in a 1965 paper, independently advocated for identifying efficient computation with a polynomial number of operations. This was an emerging idea in the mid-1960s. The identification of feasibility with a polynomial number of operations is sometimes called the Cobham–Edmonds thesis, in homage to the Church–Turing thesis.
To understand what a polynomial-time algorithm is, it is crucial to think about the running time of an algorithm, meaning how long it takes to complete its task, as the problems it is solving grow larger and larger. Consider multiplying two numbers: the more digits those numbers have, the longer it will take to compute their product, as you can see intuitively by imagining filling a board with the grade-school multiplication algorithm. The key question is not simply that the algorithm slows down as the numbers grow, but how much slower it becomes. If the numbers are twice as long, does the algorithm take twice as long? Four times as long? A thousand times as long?
The same question applies to shortest-path algorithms such as Dijkstra's algorithm: as the network grows larger, the algorithm naturally takes more time, but how much more? If the network doubles in size, does the running time double, or quadruple, or something else entirely? That is the mindset you need in order to understand what the definition of a polynomial-time algorithm really means.
A concrete way of thinking about this is in terms of Moore's Law. Moore's Law was first stated by Gordon Moore, who at the time was at Intel, in the mid-1960s. It asserted that the speed of computers doubles roughly every two years. Sometimes you hear versions citing 18 months or 12 months, and strictly speaking it concerns the number of transistors rather than raw speed, but the essential point is that computers keep getting faster at a predictable rate. Let's say twice as fast every two years.
When your computer gets significantly faster, you would hope to be able to solve significantly bigger computational problems in the same amount of time. Suppose you are willing to give the computer one hour to multiply two numbers, or to find the shortest path in a network. If you buy the next generation of computers, which is twice as fast, you would hope to multiply bigger numbers and search through bigger networks than before. But how much bigger?
What would be ideal is if a computer that is twice as fast can solve problems that are twice as large: numbers twice as big, networks twice as large. That would be the case with a linear time algorithm, which corresponds to a polynomial with no squared or cubed terms. Other polynomial algorithms still benefit from greater computing speed, though not quite as dramatically. Consider a quadratic time algorithm, such as the grade-school multiplication procedure. If you multiply two numbers each having 10 digits, you fill in roughly 10 rows of partial products across roughly 10 columns, about 100 entries in total. Multiply two 20-digit numbers and you must fill in 20 times 20, or 400 entries. The work grows as the square of the number of digits.
For a quadratic algorithm, waiting for Moore's Law to deliver computers that are twice as fast will not let you multiply numbers that are twice as large, but you do get a meaningful percentage increase: you can handle numbers about 41% larger than before, within the same fixed time budget. If the algorithm performs a cubic number of operations rather than quadratic, you still get a percentage increase from a doubling of computing power, not as large, now about 26% instead of 41%, but a genuine percentage increase nonetheless. This is precisely what we mean by a polynomial time algorithm: each doubling of computing power yields a percentage increase in the size of the problem you can solve in a given amount of time.
What, then, would a non-polynomial time algorithm look like? Consider exhaustive search over an exponentially large number of options. Think of a sequence of binary decisions: four decisions in a row means 16 options to examine; ten decisions means 1,024 options; twenty decisions means roughly one million. Every additional binary decision doubles the number of options that must be searched. If you are given a computer that is twice as fast and you are running an exhaustive search, all that extra speed buys you is one additional binary decision. Instead of handling 100 binary decisions, you can now handle 101. That is a deeply discouraging increase in problem size.
This is the formal distinction between fast and slow algorithms. With a polynomial time algorithm, doubling computing power gives you a percentage increase in the problem size you can handle. With an exponential time algorithm, doubling computing power allows you to add only a single element to the problem: the problems you can solve are barely larger than before.
P is defined as the class of "easy" problems, those solvable by polynomial-time algorithms. We already know several examples. Multiplication belongs to this class, since even the grade-school algorithm runs in polynomial time. Shortest paths is another polynomial-time solvable problem, handled by Dijkstra's algorithm. This is precisely the kind of efficient algorithm that, even now in 2026, nobody has found for the Traveling Salesperson Problem (TSP), and yet, at the same time, nobody has been able to prove that such an algorithm cannot exist.
This episode has two goals. The first is to understand easy problems, the problems in P, those that admit fast algorithms, where "fast" means polynomial-time. The second is to understand so-called NP-complete problems, which we will turn to shortly. Before doing that, however, it is worth briefly connecting our discussion to everything covered in the first episode, when we examined Turing's foundational notions of decidability and undecidability, what computers can solve in principle, and what is unsolvable even in principle.
The idea of polynomial-time solvability can be viewed as a refinement and strengthening of Turing's notion of decidability. For Turing, "solvable by a computer" meant solvable by some algorithm guaranteed to eventually halt. Here, we impose a stricter demand: the algorithm must run quickly, completing within our lifetimes, or ideally in under a second. Polynomial-time solvability is therefore a strengthening of decidability.
This raises a natural question: what is the analog of undecidability in this setting? Turing had the halting problem, a problem unsolvable by any computer. Here, we have a candidate: the TSP. We know it is not undecidable in Turing's sense, since one can always solve it by exhaustively enumerating all possibilities. The conjecture, however, is that it is unsolvable efficiently. We therefore need a precise notion of what it means for a problem to be a scaled-down version of undecidable, solvable in principle, yes, but not reliably solvable in practice.
That is the concept of NP-completeness, which will play the analog of Turing's undecidability notion. In developing it, we are also refining the Church-Turing thesis discussed back in episode one. To recall: in episode one, we encountered the seemingly quaint model of a Turing machine, and we asked whether this parable about a human computer working on a roll of tape could genuinely capture everything we could ever do with any technology for computation. The answer is yes, and that is the Church-Turing thesis, the belief that Turing machines can express any computation expressible in any other way.
The way one amasses support for that thesis is by enumerating every other known way of expressing computations and showing, one by one, that those exact same computations can be expressed using a Turing machine. That is precisely what Turing did in the appendix of his paper, where he showed that Church's lambda calculus expresses the same computations as Turing machines, and we now know the same is true for many other systems as well.
Now consider what we have just done. In episode one, we identified computation in general with what Turing machines can do. We are now identifying efficient computation with what specifically polynomial-time Turing machines can do, that is, Turing machines guaranteed to complete their task in a polynomial number of steps. This is a bolder thesis: we are claiming that the exact same formalism Turing introduced is also precisely the right formalism to capture everything there is to know about efficient computation. This claim is known as the extended Church-Turing thesis, and to be clear, it was stated by neither Church nor Turing. It came later, when attention narrowed to efficient computation.
Unlike the original Church-Turing thesis, the extended version has faced meaningful challenges, involving, for example, quantum computers. That will be a central topic in episode five. For now, having covered the first protagonist, P, the class of easy problems, and having situated our discussion within Turing's original theory, we can move on to the other main goal of this episode: understanding what the NP in P versus NP means, and specifically, what the theory of NP-completeness is.
NP-completeness is certainly one of, if not the single greatest, intellectual export from computer science to other disciplines. If you search a citation database restricting results to the natural sciences and social sciences alone, you will encounter thousands of papers discussing NP-completeness. It is extraordinarily rare for a concept this technical to cross so many disciplinary boundaries and have such broad impact. The influence NP-completeness has had in the half-century since its development is a very big deal. The story behind the terminology itself will be told in full next episode; for now, the more pressing question is why people invented this theory in the first place.
Imagine yourself in the 1960s. Brilliant researchers are cracking all kinds of algorithmic problems, yet certain problems remain stubbornly unsolved, among them the Traveling Salesperson Problem, or TSP. This led Jack Edmonds to conjecture in 1967 that the TSP simply cannot be solved by any polynomial-time algorithm. At the same time, in the wake of Turing's work, proofs of fundamental limitations on algorithms were few and far between. We have come to appreciate that algorithms can do remarkably unexpected things, Karatsuba's multiplication method being one striking example, and it is therefore extremely difficult to prove that algorithms cannot do something, Turing's theory of undecidability aside.
This creates a genuine quandary. If you care about algorithms or their limitations, and you are faced with a problem like the TSP, one for which nobody has any idea how to solve it efficiently, and nobody has any idea how to prove it cannot be solved efficiently, what do you do? It is not pragmatic for everyone to abandon all other work until the question is resolved. Most researchers conjectured, even in the 1960s as they do today, that no fast algorithm for the TSP exists, but one must be prepared for the possibility that a fully rigorous mathematical proof of that fact will take a very long time to arrive.
This is precisely where the theory of NP-completeness comes in. In the absence of a convincing mathematical proof that the TSP cannot be solved by any fast algorithm, NP-completeness provides mathematical evidence making it ever more unlikely, ever more implausible, that such a fast algorithm could exist.
This is the brilliant idea behind NP-completeness. You give up, at least temporarily, on proving difficulty in an absolute sense, proving that the TSP is hard, full stop. You pause that ambition and resort instead to relative difficulty. The goal becomes showing that the TSP is at least as hard as many, many other computational problems. That is the high-level idea of NP-completeness.
What would be the most compelling evidence of the difficulty of solving the TSP? You could say: what if the TSP were literally as difficult as every other computational problem in existence? That would be convincing. A problem as hard as every other problem anyone has ever thought of would surely be a hard problem. The trouble is that statement is known to be false. There are problems completely unsolvable even in principle by computers, such as the halting problem, and the TSP is not among them. Because there are a bounded number of easily checked candidate solutions, you can enumerate them all and remember the best, so the TSP is solvable in principle through exhaustive search.
The TSP is definitely not as hard as the halting problem, yet we still believe it is harder than, say, computing shortest paths. So what is the next most ambitious claim we could make, one that is not obviously false? Perhaps the TSP is as hard as any other problem that, like the TSP, can in principle be solved through exhaustive search over a set of easily checked solutions.
That, in fact, is going to be the definition of an NP-complete problem: a problem that is as hard as every other problem whose solutions can be recognized efficiently. When we say the TSP is hard relative to "lots of stuff," that stuff is precisely the class of problems where you know a valid solution when you see one.
Consider Sudoku. Hard Sudoku puzzles can take a very long time to solve, yet if someone else solved one and showed it to you, it would be trivial to inspect it and confirm either that the puzzle is correctly solved or that some rule has been violated, say, two identical digits appearing in the same row. Handed a solution on a silver platter, checking whether it is valid is straightforward. The same is true of the Traveling Salesman Problem. If someone showed you a route visiting all the intersections in at most an hour, it would be easy to verify that every intersection was visited and that the total travel time was within the limit.
This is precisely what we mean by an NP problem: a problem for which, given a candidate solution, it is straightforward to check whether that solution is correct. NP-completeness goes a step further: an NP-complete problem is one that is as difficult as any other problem that likewise has easily verifiable solutions, and that can therefore be solved in principle by exhaustive search.
This brings us back to Edmonds' conjecture: that there is no efficient, polynomial-time algorithm for the TSP. No one knows how to prove that formally, so the question becomes how to amass evidence for it in the absence of a proof. The strategy is one of relative difficulty: prove that the TSP is at least as hard as a large collection of other problems. The most ambitious version of this is to prove that the TSP is as hard as every problem that resembles it, that is, every problem solvable by exhaustive search through a space of easily checked solutions. That is exactly the notion of NP-completeness.
It is now known that the Traveling Salesman Problem is NP-complete. Sudoku, properly formalized, is another example, and there are thousands of others, not only in engineering, but throughout the natural and social sciences. If you stop to think about it, the very existence of NP-complete problems is remarkable. It connects back to the discussion of universality from the context of Turing's arguments around undecidability, where we encountered the idea of a universal Turing machine, a machine that takes as input the code of a program and simulates it. That was our first encounter with universality.
Here we see universality appearing in a very different form: not universal computing devices, but universal problems. An NP-complete problem such as the Traveling Salesman Problem simultaneously encodes thousands of other problems. Every problem with easily verifiable solutions is, in a precise sense, a thinly disguised version of the TSP, including Sudoku. These are not really two different problems; they are two manifestations of the same underlying problem. And that is true of all NP-complete problems.
It is remarkable when you think about it. These universal problems certainly seem like they should be hard. It would be pretty extraordinary to find a fast algorithm for even one of them. By virtue of being universal, of encoding all other problems that have easily recognizable solutions, a single fast algorithm for one NP-complete problem, say, the Traveling Salesperson Problem, would immediately solve thousands of other problems: every problem whose solutions can be efficiently verified. That is the power of universality. And it is surely suggestive that no such algorithm exists for the TSP, because if one did, the ramifications would be world-changing.
There is another consequence that becomes apparent when you think a little harder. All NP-complete problems share the same computational fate: either all of them can be solved by fast algorithms, or none of them can. Solve any one of them efficiently, and by NP-completeness you immediately solve them all. It is all or nothing. This means there are only two possible worlds we could be living in. We do not know which one, but at least there are only two.
Consider World Number I, the world as Edmonds envisioned it. We begin with the class of all problems whose solutions can be recognized quickly, the so-called NP problems. Shortest paths, multiplication, TSP, and Sudoku all belong here. Within this class, Edmonds drew a distinction: some problems, like shortest paths, are efficiently solvable, meaning a solution can not only be checked quickly but also found from scratch in polynomial time. These form the class P. Other problems, like TSP, are not efficiently solvable. The NP-complete problems are the hardest problems in NP: if you can solve any one of them, you can solve everything in NP. In World Number I, the NP-complete problems sit strictly outside P, just as Edmonds conjectured.
This clarifies what Edmonds' conjecture really says. It is not merely a claim about the TSP in isolation; it is simultaneously a claim about every NP-complete problem at once. All NP-complete problems share the same fate, so the conjecture about one is a conjecture about all of them.
World Number II is the world Edmonds was not conjecturing: the world where P equals NP. In this world, every problem whose solutions can be easily recognized also admits an algorithmic shortcut for finding those solutions. Even when the space of possibilities is astronomically large, the mere ability to verify a solution quickly would automatically guarantee the ability to find one quickly. In this world, the entire distinction between P and NP collapses: the NP-complete problems would fall inside P, and all of NP would be efficiently solvable.
What the theory of NP-completeness achieves is a dramatic compression of open questions. There are thousands of problems for which we do not know whether a fast algorithm exists. Rather than treating each as a separate mystery, NP-completeness compiles them all into a single question: is there a fast algorithm for any NP-complete problem? A fast algorithm for one gives a fast algorithm for all, and settles which of the two worlds we inhabit. The P versus NP question is precisely the question of whether we live in World Number I (where P ≠ NP) or World Number II (where P = NP).
This connects to a point raised earlier, echoing von Neumann's observation that tiny changes to a problem's description can radically alter its computational difficulty. Two problems that resemble each other closely can end up in entirely different worlds: one admitting a fast algorithm, the other being NP-complete. But there is an equally strange dual phenomenon: two problems that look nothing alike, TSP and Sudoku, for instance, can turn out to be computationally identical. Beyond both having easily verifiable solutions, they seem to share nothing. And yet they are both NP-complete, which means they are, in a precise sense, thinly disguised versions of the same problem. Tiny changes sometimes make an enormous difference; enormous changes sometimes make no difference at all when it comes to computational difficulty.
There is one more concept I owe you in this episode: what it means for one problem to be as hard as another. Recall how we have been informally defining NP-complete as hard as any NP problem, where an NP problem is simply one whose solutions are easy to recognize. Just because a solution is easy to check does not mean it is easy to find; think again of a difficult Sudoku puzzle, whose solutions are easy to verify but hard to discover. So NP-complete means a problem is as hard as any other problem whose solutions can be recognized efficiently. The natural follow-up question is: what does "as hard as" mean precisely?
The answer is a reappearance of something we discussed back in the first episode, when we covered the key ideas in Turing's argument that the halting problem is undecidable. Recall the three steps: the universal Turing machine and simulation; an adaptation of Cantor's diagonalization technique, also used by Gödel, to establish the existence of some peculiar undecidable problem; and finally a reduction from that peculiar problem to the halting problem, which spread undecidability from one to the other. We are going to do exactly the same thing here, except that this time the reductions must be efficient. We will use efficient reductions to spread NP-completeness, and more generally intractability, from one problem to another.
We are all familiar with reductions from everyday life. If you know how to get home from work, then getting home from a nearby happy hour reduces to that problem simply by walking back to the office first. If you are an Excel wizard but unfamiliar with Google Sheets, there is a reduction from the latter to the former by exporting the data into Excel. The point is that you can solve one problem easily if you know how to solve another: the first problem reduces to the second, meaning that knowing how to solve the second is sufficient to solve the first as well.
Now imagine we had a reduction from Sudoku to the Traveling Salesman Problem (TSP). You want a solution to a Sudoku puzzle, and I show you that it suffices to find a short tour visiting all intersections in a suitably constructed network. You might object that these seem like completely different problems, and constructing such reductions is genuinely an art, something one develops through training in computer science. But take it on faith that it is not unreasonable: given a Sudoku puzzle you want solved, one can construct a network such that any short traveling salesman tour in that network yields a solution to the original Sudoku puzzle. In other words, to solve Sudoku, all you need is the ability to solve TSP. That is a reduction from Sudoku to TSP, and that is precisely what we mean when we say TSP is as hard as Sudoku.
To qualify as NP-complete, however, it cannot be that just one particular problem with efficiently verifiable solutions reduces to you. It must be that every such problem does. Not just Sudoku, but literally any problem with efficiently verifiable solutions must reduce to the TSP. That is what it means for the Traveling Salesman Problem to be NP-complete. The encouraging implication is that if you could prove a problem NP-complete in this sense, where solving it would unlock fast algorithms for thousands of other problems simultaneously, that becomes compelling evidence that no fast algorithm for it exists, because the consequences of such an algorithm would be so extraordinary.
The unsettling question is: why would any problem be NP-complete at all? Why should there exist a single problem whose solution unlocks thousands of others? Without the brilliant work of the 1960s and 1970s, there is no obvious reason to believe such problems could exist, much as, before Turing's 1936 work, it was not obvious that there would be computational tasks that are fundamentally unsolvable. What we need is an analog of Turing's results on undecidability: not undecidable problems, but a scaled-down version of the same phenomenon, establishing the existence of NP-complete problems, and ideally NP-complete problems that people genuinely care about.
The analog of Turing's landmark 1936 result is work done in the early 1970s, carried out in parallel on both sides of what was then the Iron Curtain, simultaneously in North America and in the Soviet Union, and it is known as the Cook-Levin theorem. The Cook-Levin theorem, which is truly one of the most important mathematical results in all of computer science, establishes that there exist natural problems, problems we would genuinely like fast algorithms for, that are in fact NP-complete. These are problems that, on the one hand, have easily checkable solutions, but on the other hand simultaneously encode every other problem that likewise has easily checkable solutions, making them universal among NP problems in this sense.
Stephen Cook proved the theorem in North America around 1971, and Leonid Levin proved it independently in the Soviet Union at roughly the same time. Levin's work went unknown in the West for a long time, until the late 1980s or early 1990s, and for many years it was simply not known in North America and Europe that Levin had done this parallel work on NP-completeness. Today, both researchers receive equal recognition, and we call it the Cook-Levin theorem.
It is worth noting that neither Cook nor Levin actually considered the traveling salesperson problem; that was done by a third researcher, Richard Karp, whose story we will take up in the next episode. The Cook-Levin theorem establishes that natural NP-complete problems exist, a result that is hard to believe at first, and that serves as a scaled-down version of Turing's result that natural undecidable problems exist.
Once you have that initial foothold, it becomes the thin end of the wedge. As soon as Turing exhibited one natural undecidable problem, many others followed, and exactly the same story has unfolded for NP-completeness. Once you have a couple of NP-complete problems to work with, it becomes much easier to show that many, many other problems are likewise NP-complete.
That was a lot of technical content for one episode, so let me leave you with a little history, a small parable. Here is an interesting question worth reflecting on: what makes a researcher truly great? What are the key qualities required for genuinely innovative research? Talent? Obviously. Excellent mentoring? Enormously helpful. Luck? It certainly doesn't hurt. But probably one of the most important and underrated traits in doing great research is tenacity and relentlessness in the face of obstacles. In mathematical research, those obstacles come fast and furious, and the best researchers simply do not give up. That has been my consistent experience.
We were just discussing Cook and Levin, who did absolute genius work in the early 1970s inventing the theory of NP-completeness. Stephen Cook was an assistant professor in the mathematics department at Berkeley in the late 1960s, and he was denied tenure in 1970, despite having already produced a substantial body of strong work. He exacted his revenge by moving to the University of Toronto, where he remains Professor Emeritus to this day. The very next year, he invented the theory of NP-completeness, work that earned him the Turing Award in 1982. The Turing Award, if you haven't encountered it before, is the Nobel Prize of computer science. Berkeley, needless to say, came to regret that tenure decision.
Richard Karp, whom I mentioned a moment ago, was in the computer science department rather than mathematics, so he was not part of that decision, but he later reflected on it. Karp said, "It is to our everlasting shame that we," meaning he and his colleagues in computer science, "were unable to persuade the math department to give him tenure." The math department's reasoning is almost amusing in hindsight: they considered Cook's work a little too applied. For context, this was an era when computer science was still struggling to be taken seriously as an independent and rigorous discipline. Even Berkeley, which did have a computer science department at the time, was not immune to that institutional skepticism, and many other top universities had no computer science department at all. You may recall from a previous episode the dismissive remark attributed to Harvard professors in the 1970s: "We don't have a department of microscope science or telescope science, so why should we have one of computer science?" That captures the political climate surrounding Cook's difficulties at Berkeley.
Leonid Levin, meanwhile, was doing this foundational work in the Soviet Union. For various political reasons, he struggled to secure a permanent top-level academic position there, and he eventually immigrated to the United States in 1978. He completed a second PhD very quickly at MIT and then joined Boston University, where he remains a professor to this day. He was awarded the Knuth Prize, the lifetime achievement award in theoretical computer science, in 2012. One can reasonably assume he would have shared the Turing Award with Cook had his work been known in the West at the time, but during the Cold War, advances made in the Soviet Union reached North America and Europe only very slowly.
The point of these stories extends well beyond research. When we look at highly successful people, their achievements can sometimes appear almost effortless or preordained, as though there were never any other way the story could have ended. But in my experience, having gotten to know many great researchers well over the years, they almost invariably had to push through a series of genuinely formidable obstacles, both mathematical and otherwise, to arrive where they are. I'll leave you with that thought. Get excited, because the next episode is a deep dive into the P versus NP question. I'll see you there.