Stephen Cook

Life and career

Stephen Arthur Cook was born in Buffalo, New York, in 1939, and grew up in nearby Clarence. His father worked as a chemist and taught at the University of Buffalo; his early exposure to technical work came partly through a local inventor for whom he did odd jobs. He went to the University of Michigan for his undergraduate degree and then to Harvard, where he completed a PhD in mathematics in 1966. His thesis was on the complexity of multiplication — specifically, on how fast machines of various kinds can multiply numbers — which is a revealing starting point. Even at the outset, the question that interested him was not *can this be computed* (Turing had settled that) but *how much does it cost*.

Cook took a position at the University of California, Berkeley, in the mathematics department. He was not granted tenure there — a decision that has become one of the more frequently cited administrative embarrassments in the history of the field, since the paper that founded an entire discipline appeared within a few years of his departure. In 1970 he moved to the University of Toronto, where he joined the computer science department and remained for the rest of his career. Toronto suited him. He is by every account a soft-spoken, exacting, almost self-effacing person, uninterested in the promotional machinery of academic life and content to work quietly on the hardest available question.

In 1971 he presented "The Complexity of Theorem-Proving Procedures" at the third ACM Symposium on Theory of Computing. It is nine pages long. It introduced the class NP, the notion of polynomial-time reducibility in the form now used, and the theorem that Boolean satisfiability is complete for NP — meaning every problem in the class reduces to it. Richard Karp read it and within a year produced his famous list of twenty-one problems shown NP-complete by reduction from Cook's, at which point the field understood what had happened. Unknown to either of them, Leonid Levin had independently arrived at essentially the same result in the Soviet Union; the theorem is now often called Cook–Levin.

Cook received the Turing Award in 1982 for that work. He has also received the Killam Prize, the Bernard Bolzano Medal, and the John L. Synge Award, and he is a Fellow of the Royal Society and the Royal Society of Canada. When the Clay Mathematics Institute assembled its seven Millennium Prize Problems in 2000, Cook was asked to write the official problem statement for P versus NP — a fitting assignment, since the question is essentially his. He continued at Toronto for decades, supervising students, working on proof complexity and bounded arithmetic, and quietly declining to overstate what anyone knows about whether P equals NP. He is widely reported to suspect they are not equal, while stressing that nobody has any real idea how to prove it.

Key contributions

**The Cook–Levin theorem and NP-completeness.** The 1971 construction is worth understanding concretely, because its technique is the whole point. Take any problem whose candidate solutions can be *checked* in polynomial time — that is, any problem in NP. Formally that means there is a nondeterministic Turing machine that decides it in polynomial time. Cook showed how to take that machine and an input, and mechanically write down a Boolean formula that is satisfiable if and only if the machine has an accepting computation on that input. The formula's variables encode the entire computation history — which symbol is in which tape cell at which time step, which state the machine is in — and its clauses encode the local consistency conditions that make a tape history a legal computation. The construction is polynomial in size. Therefore, if you could solve satisfiability quickly, you could solve *everything in NP* quickly.

This is a strange and powerful kind of statement. It says that a single, concrete, rather mundane problem — is there an assignment of true/false to these variables making this formula true? — is a universal hardness certificate. Karp's follow-up showed that the property propagates: reduce SAT to your problem and your problem inherits the status. Today thousands of problems across scheduling, graph theory, logistics, biology, and verification are known to be NP-complete, and proving that a new problem is NP-complete is a standard, teachable move. Its practical value is negative but enormous: it tells a working researcher to stop looking for an exact polynomial algorithm and start designing approximations, heuristics, parameterized algorithms, or average-case methods. Half of modern algorithm engineering is a response to Cook's theorem.

**P versus NP.** Cook also stated the question that follows. P is the class of problems solvable in polynomial time; NP the class whose solutions are verifiable in polynomial time. Is finding as easy as checking? Every intuition, every failed attempt, and half a century of accumulated evidence suggests not — but there is no proof, and the known barriers (relativization, natural proofs, algebrization) have systematically ruled out the obvious approaches. The question is now a Millennium Prize Problem and is generally regarded as the deepest open problem in computer science, with implications well beyond it: if P = NP, essentially all of modern cryptography collapses, and mathematical creativity itself becomes mechanically automatable in a strong sense.

**Proof complexity and bounded arithmetic.** Cook's later research is less famous but is a serious research program in its own right. With Robert Reckhow he founded **propositional proof complexity**, which asks how long the *shortest proof* of a tautology must be in a given proof system. The Cook–Reckhow framing connects this directly to complexity classes: NP equals co-NP if and only if there exists a propositional proof system in which every tautology has a short proof. This gives a concrete, incremental research program aimed at a question that resists frontal assault — prove superpolynomial lower bounds for stronger and stronger proof systems and you inch toward separating the classes. He also developed **bounded arithmetic**, notably the equational theory PV, a formal system whose provably total functions are exactly the polynomial-time computable ones. This makes complexity classes into logical theories, so that questions about efficient computation become questions about what weak formal systems can prove. Cook additionally introduced the complexity class SC (sometimes called "Steve's Class"), covering problems solvable simultaneously in polynomial time and polylogarithmic space.

In battle

Cook's computed profile is the sharpest specialization on the roster. He carries 103 problems at a mean of 37.8, with a range from 3 to 98 — a bimodal fighter who either owns a problem outright or has literally nothing to contribute. His top category is **computability** at 68.2 across sixteen problems, followed by **search** (44.1), **high-dim** (43.0), and **networks** (41.9).

His two ceiling problems are both, in effect, his own theorem. **P158, "The problem all others reduce to"** (98) is the Cook–Levin theorem itself; the game's explanation notes that the only reason the score is not 100 is Levin's independent Soviet discovery. **P187, "Solve the impossible formula"** (98) is SAT solving, the practical descendant. **P031, "Is there a fast route through every city?"** (97) is Hamiltonian path / TSP, one of the canonical NP-complete problems reachable by a short reduction from SAT. **P162, "More time, strictly more power"** (93) is the time hierarchy — foundational complexity territory. **P269, "Frequencies without interference"** (93) is graph coloring in applied dress, and Cook's response to it is exactly right: recognize the NP-complete core, then reason about what can be salvaged. **P030, "Will it ever halt?"** (88), **P164, "Trust without recomputing"** (82, interactive proofs), and **P178, "The variables that must be whole"** (82, integer programming) round out his dominant set.

The losses are stark and worth studying. Cook's floor is **P136, "Counting accidents"** (3) — Poisson regression for insurance claims. **P134, "When the predictors move together"** (5) is multicollinearity and ridge regression. **P015, "Does the model fit at all?"** (10) is goodness-of-fit testing. **P107, "The thousand-year flood from thirty years"** (8) is extreme-value theory; **P117, "Randomize the villages, not the people"** (8) is cluster-randomized trial design; **P201, "The dice make it learnable"** (8) is a probabilistic-learning framing that requires PAC-style statistical reasoning Cook never worked in. His `regression` average is 4.0 and his `small-sample` average is 10.0 — the two lowest categories on his card.

The structural point a student should take from this: NP-completeness is a theory about *worst-case exact computation on combinatorial structures*. It has nothing to say about noise, estimation, sampling variability, or inference from data. Cook is devastating against any problem whose difficulty is combinatorial and whose answer is a yes/no about existence of a structure — routing, scheduling, coloring, satisfiability, resource allocation with integrality constraints. He is helpless against any problem whose difficulty is statistical. Thirty-one of his 103 problems fall at or below 20. Fielding Cook is a bet that the round will be about hardness, not about data; when that bet is right it is close to a guaranteed win, and when it is wrong it is a shutout in the other direction.