IT PAPERS DEEP-READ · PAPER 52
Stephen Cook · University of Toronto · STOC 1971
In 1971, Stephen Cook proved something that has vexed computer science ever since: there is a huge family of problems where checking whether an answer is correct is easy, but finding the answer from scratch may be hopelessly hard — and they are, in essence, all the same problem, so cracking any one of them cracks the lot. This is the origin of the famous open question P versus NP.
Some things you can check in a glance once the answer is handed to you, yet finding that answer yourself is brutal. A box of jigsaw pieces: once it's assembled you see in a second whether it's right — but building it from loose pieces can eat a whole day. Seating a big dinner table under a pile of "these two can't sit together" rules: hand me a finished chart and I can check it instantly, but producing one from nothing gets hopeless as the crowd grows. Cook noticed that such "easy to check, seemingly brutal to solve" problems are countless — and that they are all wired together.
Cook did two things. First, he fenced off this whole family of "easy-to-check" problems (later named NP). Second — and this is the stunning part — he proved that one problem in the family (deciding whether a string of logical conditions can all be satisfied at once, called satisfiability) is the hardest representative: any problem in the family can be quickly rewritten into that one problem.
The key tool is rewriting (the technical name is a reduction). If I can quickly translate problem A into problem B — so A's answer is hidden inside B's answer — then "B is easy" implies "A is easy" too. Cook proved that every problem in the vast NP family can be translated this way into that one satisfiability problem. So it becomes a master key: if anyone finds a fast, general method to crack it, the entire family — thousands of seemingly unrelated hard problems — falls open all at once. Conversely, decades of nobody managing it have made people increasingly suspect that no such fast method exists.
"Does P actually equal NP?" became the single biggest open question in computer science, with a million-dollar prize still unclaimed. The practical payoff is large too: the moment you discover your hard problem belongs to the same family as that master key, you've essentially received a notice — stop hoping for a perfect-and-lightning-fast algorithm, and make do with approximations and clever shortcuts. One honest caveat: "hardest" means the worst case — in practice, many concrete instances of these problems are still solved quickly and well by today's solvers, so "same family" doesn't mean "this particular instance is forever unsolvable."
Cook proved that within the big family of "easy-to-check" problems there is a hardest representative — crack it and you crack them all — and to this day nobody knows whether such a crack even exists. That is P versus NP.
Want the precise definitions of P and NP, how Cook's theorem is proved, and the diagram that "writes a computation as a logic puzzle"? → Switch to the Deep read
Cook's 1971 paper defined the class of problems whose answers can be verified in polynomial time (later called NP), introduced polynomial-time reductions for comparing the difficulty of problems, and proved the first NP-complete problem — the satisfiability (SAT) of propositional formulas: every problem in NP reduces to it in polynomial time. SAT thus became the "hardest representative" of all of NP, turning "does P equal NP?" from a vague intuition into a precise mathematical question.
By Stephen Cook, presented at the third annual ACM Symposium on Theory of Computing (STOC) in 1971. It stands on Turing (1936, computability) and 1960s complexity theory (Hartmanis–Stearns and others making "how much resource does it take" itself the object of study), giving "hard to solve" its first precise, workable characterization. A year later Karp (1972) used it to prove 21 classic problems NP-complete, carrying the theory into the whole of algorithm design. The Soviet mathematician Levin obtained an equivalent result independently and almost simultaneously, so it is also called the Cook–Levin theorem. Cook received the 1982 Turing Award for it.
By the 1960s, people could already separate "has an algorithm" from "has none" (computability, the line Turing drew). But within "has an algorithm" lay a vast gulf: testing whether a number is prime, or finding a shortest path in a graph, have fast algorithms; yet other problems — "can this map be 3-colored?", "can this batch of goods be packed exactly into a few bins?" — had only one known general method: try every possibility one by one, with the count exploding exponentially as the input grows. People sensed vaguely that such problems were "intrinsically harder," but couldn't say what "hard" even meant, let alone prove they truly had no fast algorithm. What was missing was a common yardstick: how do you say precisely that "problem A is at least as hard as problem B"? Cook's paper built that yardstick.
P: decision problems with a deterministic polynomial-time algorithm — "efficiently solvable." NP: for a "yes" instance, if there exists a certificate / answer of polynomial length that can be verified as valid in polynomial time, the problem is in NP — "answers can be efficiently verified." Equivalently, NP is the class decidable by a nondeterministic Turing machine in polynomial time (the machine "guesses" the certificate, then verifies). Example: SAT is in NP — hand over an assignment of the variables as a certificate, plug it into the formula, and you know at once whether it's true. Clearly P ⊆ NP (if you can solve it you can verify it). The suspense is the converse: does P = NP? Is everything efficiently verifiable also efficiently solvable?
Cook defined the polynomial-time reduction: if a polynomial-time procedure can turn every instance of A into an instance of B while preserving the answer (A is "yes" iff the produced B is "yes"), write A ≤ B, meaning "A is no harder than B" — because once you have a fast method for B, you can translate then solve B, incidentally solving A fast. Reductions are transitive and composable. With this yardstick, "which is hardest" acquires an exact meaning for the first time.
If every problem in NP reduces to L, and L is itself in NP, then L is NP-complete — the "hardest representative" of NP: solve any one NP-complete problem (put it in P) and all of NP collapses into P, so P = NP at once. Cook's theorem: SAT is NP-complete. (Cook's original text phrased it via the "tautology" — always-true — decision, which is the complementary, equivalent form of SAT.) Behind this line is a startling fact: one concrete logical decision problem concentrates the entire difficulty of NP.
How do you prove that the wildly assorted problems in NP all turn into SAT? Cook's trick is not to match problems one by one, but to target "the machine that verifies it." Behind any NP problem sits a nondeterministic Turing machine M that decides it within a polynomial number of steps. Spread M's entire run on input x into a tableau: rows are time steps, columns are tape cells, each cell recording the symbol at that moment, plus the head position and machine state.
Then describe every cell of the tableau with boolean variables, and nail down the "rules of the game" with a set of clauses: ① the first row must be exactly the input x; ② each pair of adjacent rows must obey M's transition rules (every step legal); ③ an accepting state appears in some row. The formula φ so assembled is satisfiable ⟺ M has a run that reaches accept. And since the tableau is only polynomially large, so is φ — and it can be built in polynomial time. Thus "does M accept x?" is translated into "is φ satisfiable?" — every NP problem ≤ SAT, and the theorem is proved. The key insight: satisfiability is "universal" enough to encode the very fact of whether each step of a computation is legal.
This is a theory paper — no benchmarks, but the conclusions it delivers are checkable and hard:
It gave "hard to solve" a precise, operational definition and laid down the central structure of computational complexity theory: P, NP, reduction, completeness. From it:
n¹⁰⁰ is also polynomial; conversely, some exponential algorithms are fine at small scale. It's a convenient theoretical convention, not always matching real-world efficiency.① One line: Cook defined NP, used polynomial reductions to compare difficulty, and proved SAT is the first NP-complete problem.
② Pain point: even within the computable lies a vast gulf — some problems admit only "try every possibility," yet there was no precise notion of "harder."
③ Two classes: P = efficiently solvable; NP = answers efficiently verifiable (equivalently, nondeterministic polynomial time); clearly P⊆NP — is P=NP?
④ Yardstick: polynomial-time reduction A ≤ B — "if B is easy so is A" — giving "hardest" its first definition.
⑤ Completeness: NP-complete = the hardest representative of NP; solve any one and all of NP collapses into P.
⑥ Cook's theorem: SAT is NP-complete; proved by encoding "does a given nondeterministic machine accept?" as a satisfiability formula (run tableau → boolean clauses).
⑦ Impact: Karp promptly found 21, now thousands; a signpost for algorithm design, birth of SAT solvers; P vs NP a Millennium Problem, Cook a Turing laureate.
⑧ Limits: P vs NP still open; NP-completeness is worst-case, not always hard in practice; polynomial ≠ always practical; Levin discovered it independently (Cook–Levin).