A First Taste of Algorithms · Epilogue: The Edge of the Map

Easy to check, hard to find

The halting problem is a wall: solving it is impossible. The second edge of the map is stranger, because no one knows whether it is a wall or a door. It is the most important open question in this subject, and one of the deepest in all of mathematics, and you can understand exactly what it asks.

Some problems are hard to solve but easy to check. A finished jigsaw is obviously finished — one glance. Finding the arrangement took hours; verifying it takes a second. A sudoku solution is checked in a moment; finding it is work. This gap — between finding an answer and recognizing a correct one — has a precise form, and a name.

Consider a concrete puzzle, the granddaddy of them all. You are given a logical formula: a string of true/false variables joined by ANDs and ORs, like (a or b or not-c) and (not-a or c or d) and …, with hundreds of variables and clauses. The question: is there any setting of the variables that makes the whole thing true? This is satisfiability, and notice its two faces. If someone hands you a setting that works, you check it in an eyeblink — plug in the values, evaluate each clause, done, a few hundred steps. But finding a setting, with no one to hand you one? The obvious method is Chapter 1’s enemy: try all 2ⁿ settings, an exponential wall, hopeless past a few dozen variables. Centuries of cleverness have not found a fast method, and satisfiability is not alone — thousands of problems, from scheduling to protein folding to optimal routing, share its exact character: a solution is checkable in polynomial time (the “easy” growth shapes of this book — n, n², n log n); a solution seems to require exponential time to find.

Call the easy-to-solve problems P (solvable in polynomial time — everything this book built fast algorithms for). Call the easy-to-check problems NP (a proposed solution is verifiable in polynomial time — satisfiability, and its thousands of cousins). Every P problem is obviously in NP: if you can solve it fast, you can check a solution fast by solving it yourself. The question — the whole question — is whether it goes the other way:

Is P equal to NP? Is every problem whose solutions are easy to check also a problem whose solutions are easy to find?

If P = NP, then finding is secretly no harder than checking — there is a fast algorithm for satisfiability, for thousands of problems we believe are hard, and almost every optimization humanity cares about falls at once. Much of modern cryptography, which rests on certain problems being hard to solve but easy to check, would dissolve; so would much of the difficulty of science. If P ≠ NP, then some problems are genuinely, permanently hard to solve despite being trivial to verify — finding really is harder than recognizing, and the exponential wall around satisfiability is real and forever.

Almost everyone who studies it believes P ≠ NP. No one has proved it. The problem was crisply posed around 1971, by Stephen Cook and Leonid Levin — independently, on two sides of a closed border, the book’s recurring pattern one final time. It carries a million-dollar prize, unclaimed. It is, very possibly, the deepest question this book could point at, and it remains exactly as open today as the day it was asked. The honest sentence, the one this whole book has been teaching you to say: we do not know, and the not-knowing is not a gap in your education — it is the live edge of human knowledge, and you are now standing on it.

Deeper water: the strange unity of the hard problems

One fact makes P vs NP sharper than “some problems seem hard.” In 1971 Cook proved that satisfiability is NP-complete: every single problem in NP can be efficiently translated into a satisfiability question. Then Richard Karp, in 1972, showed twenty-one classic problems — scheduling, graph coloring, the traveling salesman among them — are NP-complete too, and the list has since grown to thousands. They are, in a precise sense, the same problem in different clothes: a fast algorithm for any one of them would yield a fast algorithm for all of them, and would prove P = NP. They stand or fall together. This is why the question is not a curiosity about one puzzle but a hinge under all of computation: thousands of independent walls turn out to be one wall, and no one knows if it has a door. (The translation between them, by the way, is itself an algorithm — efficient, constructive, the book’s own machinery turned to map one problem onto another. Even the study of impossibility is done with algorithms.)

All 32 chapters of A First Taste of Algorithms · Foundations · All courses