06 · The Wall

THE SHORTEST PATH — A History of the Art and Science of Problem-Solving

A letter to a dying man

In the spring of 1956, John von Neumann was fifty-three years old and dying of cancer, confined increasingly to Walter Reed hospital, his once-astonishing productivity narrowing to whatever his failing body would allow. Kurt Gödel — his old friend from Vienna, the logician who had shattered Hilbert's dream of a complete and consistent mathematics twenty-five years earlier — wrote to him that March, and by most accounts the letter was partly an attempt to give a brilliant, dying mind something to chew on besides its own decline.

The question Gödel posed was technical, almost casual in its phrasing, and it would take computer science another decade and a half to realize what he had actually asked. Consider a mathematical statement of a certain length. Checking whether a proposed proof of that statement is correct can obviously be done quickly — you just verify each step. But how long does it take to find a proof at all, if one exists? Gödel wanted to know whether this search could always be done in time roughly proportional to the length of the statement (or its square), rather than growing explosively as statements get longer. He was, in effect, asking whether finding is fundamentally harder than checking — the question that decades later would be given the name P versus NP (Cornell eCommons, "Gödel, von Neumann and the P=?NP Problem"; Panda Notes, "Gödel's Letter to von Neumann"). Von Neumann died the following February. Whether he ever replied is not known; no response survives. The question sat, essentially unnoticed outside a small circle, for fifteen more years.

This chapter is about what happened when the question was finally answered — not solved, but given a precise shape and a name — and about the strange, double-edged discovery that followed: that some problems appear to resist every clever reframing this book has celebrated so far, and that this resistance, once proven, becomes a kind of knowledge in its own right.

One Disease, Many Symptoms

The formal birth of the field came in 1971, when Stephen Cook, then at the University of Toronto, published a short paper titled "The Complexity of Theorem-Proving Procedures." Cook studied the Boolean satisfiability problem, SAT: given a logical formula built from variables that can each be TRUE or FALSE, connected by ANDs, ORs, and NOTs, is there some assignment of values that makes the whole formula true? Checking a proposed assignment is trivial — plug in the values and evaluate. Finding one, when the formula has thousands of variables locked together by thousands of constraints, seemed to require something close to trying all possibilities.

Cook's insight was not to solve SAT faster. It was to show that SAT is, in a precise sense, the hardest problem of its kind: any problem whose solutions can be quickly checked (this class is called NP, for "nondeterministic polynomial time") can be systematically translated — "reduced" — into an equivalent instance of SAT, using only a modest, efficient amount of computation to perform the translation. If you could solve SAT quickly, you could solve anything checkable-in-NP quickly, by first translating it into SAT. This property earned SAT the label NP-complete: complete, in the sense of capturing the full difficulty of the entire class (GeeksforGeeks, "Cook–Levin Theorem"). Working independently and in near-total isolation behind the Iron Curtain, the Soviet mathematician Leonid Levin arrived at essentially the same result at almost the same time, framed slightly differently, around 1973 — a discovery so cleanly convergent that the result now carries both names, the Cook–Levin theorem, an acknowledgment that important mathematical truths sometimes get discovered twice by people who have never read each other's work.

It helps to make the checking-versus-finding distinction concrete with something more familiar than Boolean formulas. Take a hard Sudoku puzzle. If a friend hands you a completed grid and claims it solves the puzzle, verifying the claim is almost mechanical: scan each row, column, and box for repeated digits, and you are done in seconds, however large the grid. But finding that completed grid in the first place, starting from a sparse set of clues, can require searching through a genuinely enormous space of candidate fillings — there is no known shortcut that scales as gracefully as the checking does. Sudoku, scaled up to arbitrary grid sizes, is itself known to be NP-complete. Every problem on this chapter's list shares that same lopsidedness: an answer that is cheap to confirm and, as far as anyone has proven, expensive to construct.

What a reduction actually does, in the vocabulary this book has been building, deserves to be named as a move in its own right, because it is one of the most powerful weapons a solver can pick up. A reduction says: your problem, however unfamiliar it looks, is secretly a disguised copy of a problem someone has already fully understood. Translate your instance into the known problem's language, solve that, translate the answer back. This is the same act of recognition that let chapter 04's operations researchers see a plywood mill and a wartime diet as the same linear program in different clothes — except here the recognition cuts the opposite way. Instead of finding a shortcut, a reduction can prove that no shortcut is possible, by showing that your problem is at least as hard as one already known to resist every attempt at a shortcut.

Karp's Rogues' Gallery

Cook's theorem proved that one problem, SAT, was the hardest of its class. It took Richard Karp's 1972 paper, "Reducibility Among Combinatorial Problems," to show the world how crowded that class actually was. Karp took Cook's result and, using nothing but a chain of reductions, showed that twenty-one further problems — familiar, practical, seemingly unrelated problems that engineers and planners had been quietly struggling with for years — were all secretly NP-complete too (Karp, "Reducibility Among Combinatorial Problems" (1972); Wikipedia, "Karp's 21 NP-complete problems").

Karp's list reads like a tour of applied mathematics: whether a graph can be colored with a given number of colors so that no two connected nodes share one; whether a set of items can be partitioned into two piles of equal total value; whether a network can be covered by a small set of chosen nodes touching every edge; whether a Boolean formula in a certain restricted form is satisfiable at all. These problems had been attacked, separately, by graph theorists, operations researchers, and logicians who had no particular reason to think their struggles were connected. Karp's chain of reductions revealed they were all the same disease wearing twenty-one different costumes — precisely the discovery chapter 04 celebrated in Kantorovich's plywood and Stigler's diet, except that here the shared identity is a shared curse rather than a shared shortcut. If you found an efficient algorithm for any one of them, you would have found one for all of them, and for every problem in NP besides. Nobody has ever found one. Nobody has proven that nobody can. That gap — between decades of failed attempts and a rigorous proof of impossibility — is exactly where the Millennium Prize question lives.

The Million-Dollar Question

In 2000, the Clay Mathematics Institute selected seven problems it judged to be the deepest open questions in mathematics and placed a one-million-dollar prize on the first correct solution to each. P versus NP is one of the seven — formally, does every problem whose solutions can be efficiently verified also admit an efficient method of discovery? — and as of this writing it remains unsolved, one of six of the original seven still standing; only the Poincaré conjecture has fallen, to Grigori Perelman in the early 2000s (Clay Mathematics Institute, "P vs NP"; Wikipedia, "Millennium Prize Problems").

The traveling salesman problem has become this chapter's emblem, and for good reason: it is easy enough to state to a child (find the shortest possible route visiting every city on a list exactly once and returning home) and hard enough that no one has ever found a way to solve it exactly, for large instances, that beats trying an amount of work growing explosively with the number of cities. It sits, alongside SAT and Karp's twenty-one, on the far side of the wall — not proven impossible to solve quickly, but proven exactly as hard as every other problem in the same enormous, unresolved family.

It is worth pausing to be honest about what "the wall" actually claims, because it is easy to overstate. Nobody has proven P ≠ NP. It remains logically possible — though almost no computer scientist believes it — that some ingenious algorithm for SAT is waiting to be found, and that finding it would efficiently solve every problem on Karp's list and every problem like them at a stroke. What has been proven, with total rigor, is the equivalence: solve one member of this vast family efficiently and you have solved them all. The wall may or may not be permanent. What is certain is that it is the same wall, everywhere you press against it.

Life at the Wall

If the theory stopped here, this would be a chapter about despair: a proof that a huge swath of practically important problems cannot be solved exactly and efficiently, full stop. What actually happened next is more interesting, and it is the part of this chapter's story that keeps this book's central thesis alive even at its darkest point — because solvers, faced with a wall, did not stop. They found doors.

The first door is approximation: give up on finding the provably optimal answer and settle, deliberately, for a solution guaranteed to be within some fixed, known factor of optimal. In 1976, Nicos Christofides published an algorithm for a common variant of the traveling salesman problem — one where the triangle inequality holds, meaning a direct route between two cities is never longer than a detour through a third — that is guaranteed to find a tour no more than 50 percent longer than the true shortest possible tour, no matter the instance. Remarkably, more than four decades later, Christofides' 1.5-factor guarantee for this problem had still not been beaten by any published algorithm as of the early 2020s, a striking testament to how hard even bounded progress on an NP-complete problem can be (arXiv, "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem"). An approximation algorithm does not defeat the wall. It negotiates terms with it: not the best answer, but a provably good-enough one, delivered in a time that does not explode.

The second door is randomization — the same willingness to trade certainty for speed that chapter 04 met in Monte Carlo methods, applied here to combinatorial search rather than physical simulation. A randomized algorithm makes some of its choices by coin flip rather than exhaustive comparison, and for many hard problems this yields algorithms that are fast on average and wrong only with controllable, vanishingly small probability — a guaranteed-correct answer traded for an almost-certainly-correct one delivered far sooner. The clearest everyday example sits, fittingly, inside the very cryptography this chapter is about to turn to: before RSA can lock anything, it first needs two very large prime numbers, and testing an enormous candidate number for primality by trial division is itself hopelessly slow. The Miller–Rabin test, devised by Gary Miller in 1976 and made fully practical by Michael Rabin shortly after, picks random witnesses and checks each one against the candidate number; a composite number will be caught with at least even odds by any single random witness, so after fifty independent draws the chance of a wrong answer falls below one in a quadrillion — small enough that every RSA key generated today is built on primes accepted by a test that is not, strictly, certain, only certain enough (Cornell CS4820, "The Miller-Rabin Randomized Primality Test").

The third door is the most surprising, and it is the one modern computing quietly walks through every day without most of its users ever noticing. In the decades since Cook and Levin's theorem, engineers built increasingly sophisticated SAT solvers — programs that attempt to find a satisfying assignment for exactly the problem Cook proved NP-complete in the first place. The modern generation of these tools, built around a technique called conflict-driven clause learning (CDCL), does something that should, on paper, be impossible: it routinely solves real-world SAT instances with millions of variables and clauses, arising from chip verification, software testing, and scheduling, in practical amounts of time (arXiv, "Relating Complexity-theoretic Parameters with SAT Solver Performance"). CDCL works by learning from its own failures mid-search: every time it reaches a dead end, it derives a new logical constraint — a "clause" — summarizing why that dead end occurred, adds it permanently to the problem, and uses it to prune away every future branch that would repeat the same mistake for the same underlying reason. Over the course of a long search, the solver effectively rewrites the problem it is solving, filling it with accumulated scar tissue from every wrong turn, and the accumulated scars turn out to make the remaining search dramatically smaller. This does not contradict the Cook–Levin theorem. Worst-case instances of SAT, carefully constructed to defeat exactly this kind of learning, remain exponentially hard, and always will unless P equals NP. But the industrial instances that show up in real chip designs and real schedules are, empirically, richly structured rather than adversarially worst-case, and researchers have spent years trying to characterize exactly what kind of hidden structure — community clustering, "backdoor" variable sets, low treewidth — CDCL solvers are quietly exploiting to walk straight through problems that complexity theory says should be untouchable. The wall is real, in the worst case, for every instance anyone could construct. It is also, for the instances that actually show up in practice, full of doors nobody predicted would be there.

The Wall as Fortress

The final turn in this chapter's story inverts everything that came before it, and it is the most consequential inversion in this book. Every solver so far has treated hardness as an obstacle: a wall to be reduced away from, approximated around, or randomized through. In 1977, three MIT researchers — Ron Rivest, Adi Shamir, and Leonard Adleman — realized that hardness could instead be the product.

Their cryptosystem, which took the researchers' initials as its name, RSA, is built on a specific, carefully chosen instance of computational hardness: multiplying two very large prime numbers together is fast, taking a computer a fraction of a second even for numbers hundreds of digits long, but factoring the resulting product back into its two original primes, without already knowing them, has no known efficient method — you are back to something resembling brute-force search through an astronomically large space of candidate factors (Splunk, "RSA Algorithm in Cryptography: Rivest Shamir Adleman Explained"). Anyone can publish the product — the "public key" — and use it to lock a message. Only someone who knows the two original primes — the "private key" — can unlock it efficiently; everyone else faces a computational wall as real as any traveling salesman's. RSA is, technically, believed to rely on the hardness of integer factorization rather than being proven NP-complete in the strict Cook–Levin sense — factorization sits in a curious, not-fully-resolved corner of complexity theory, apparently hard but not known to be NP-complete itself. What matters for this chapter's purposes is the philosophical hinge, not the technical fine print: an entire branch of applied mathematics discovered that a wall no one can climb is exactly as valuable as a treasure no one can steal. Every secure connection to a bank, a hospital record, or an encrypted message rests, at bottom, on the same kind of hardness that makes the traveling salesman problem resist every solver's cleverness. One field's dead end is another field's foundation.

Hardness Is Information

Step back, and this chapter completes something chapter 00 promised and chapter 04 and 05 built toward: the honest limits of this book's central claim. "Great solvers do not search harder; they change the space until the path is short" has held, gloriously, across every chapter so far — Euler's dots, Blackett's convoys, Dijkstra's frontier, A*'s admissible optimism. NP-completeness is this book's proof that the claim has a genuine boundary. Some spaces, as far as anyone has ever proven or is likely to prove soon, cannot be compressed by any representation change, however clever — not because no one has been clever enough yet, but because Cook, Levin, and Karp showed that compressing any one of them efficiently would compress all of them efficiently, and seventy years of the finest minds in computer science trying to do exactly that have come back empty-handed.

But notice what kind of knowledge that failure actually is. Knowing that a problem sits behind the NP-complete wall is not the absence of a solution — it is a piece of information about the problem, as concrete and useful as knowing its size or its symmetries. It tells you, immediately, not to waste a career hunting for an exact, always-fast algorithm. It tells you to reach instead for approximation, randomization, or a solver built to exploit whatever real-world structure your instances actually have, rather than their theoretical worst case. And, in RSA's case, it tells you the wall itself might be worth more standing than knocked down. Naming the wall is itself an act of solving — it is the last, hardest-won representation change this section of the book has to offer: reframing "I cannot find a fast algorithm" from a personal failure into a proven structural fact about the space, and then choosing, with open eyes, which door to walk through instead.

The Move

Move 06 — Name the wall, then trade: reduce, approximate, randomize, or repurpose the hardness.

• Before searching for years, check whether your problem is a known monster in disguise. A reduction from a Karp-list problem, or from SAT itself, is proof that no one else has found a fast general solution either — that is worth knowing before, not after, a career's worth of failed attempts.
• When exact and fast cannot both be had, choose which one to give up, deliberately. Christofides' bound trades exactness for a guaranteed-good approximation; Monte Carlo-style randomization trades certainty for overwhelming probability. Both are engineering decisions, not defeats.
• Check whether your actual instances are the adversarial worst case or the friendly common case. CDCL solvers prove that "NP-complete in theory" and "intractable in your specific data" are different claims; industrial SAT is proof that real problems are often far kinder than the theorems that bound them.
• Ask whether the hardness itself has value. RSA shows that a wall no one can climb can be turned into a fortress. Before treating intractability as pure obstacle, ask who would pay for a problem that stays hard forever.

Next — Chapter 07 · Gallery I: The Single Move: theory now gives way to a gallery. Five solvers, four centuries, one move each — the history this book has built in the abstract, made concrete, one great solve at a time.