Skip to content

Cook and Levin: NP-Completeness on Two Sides of the Iron Curtain

Abstract

In 1971 a mathematician in Toronto and a graduate student in Moscow, unaware of each other and separated by the Cold War, arrived at the same discovery: that a single problem could stand in for an entire universe of hard problems, so that solving it efficiently would solve all of them at once. Stephen Cook published first in an American conference proceedings; Leonid Levin’s version sat blocked by Soviet bureaucracy for years. The result they shared, the Cook-Levin theorem, defined NP-completeness and set up P versus NP, the question now worth a million dollars and still open.

The Man Berkeley Let Go

Stephen Cook was born in Buffalo, New York, in 1939, took his doctorate at Harvard, and joined the mathematics department at Berkeley in 1966. In 1970 the department denied him tenure. It was, by the later admission of one of his own field’s founders, a historic misjudgment: Richard Karp said “it is to our everlasting shame that we were unable to persuade the math department to give him tenure.” Cook moved to the University of Toronto, and the next year, in 1971, presented “The Complexity of Theorem-Proving Procedures” at the newly founded ACM Symposium on Theory of Computing.

The paper isolated one problem, Boolean satisfiability (SAT): given a logical formula of ANDs, ORs, and NOTs, is there any assignment of true/false to its variables that makes the whole thing true? Cook proved that SAT is NP-complete, meaning two things at once. SAT is in NP, the class of problems whose proposed solutions can be checked quickly. And every other problem in NP can be transformed into a SAT instance in polynomial time. That second half is the shock. SAT is not merely one hard problem; it is a universal one. A fast algorithm for SAT would be a fast algorithm for every problem in NP, which includes thousands of the practical optimization and search problems that industry cares about. The question of whether such an algorithm exists is the question of whether P equals NP.

The Man the Soviet System Held Back

While Cook was writing in Toronto, Leonid Levin was reaching the same summit from the Moscow side. Born in Dnipropetrovsk in 1948, Levin was a student of Andrey Kolmogorov at Moscow University, finishing his master’s in 1970. He had been lecturing on the core idea for some years: that there exist universal search problems, problems as hard as any in a broad class, and that a good algorithm for one would solve them all. Levin’s formulation was in terms of search rather than yes/no decision, and he identified six such universal problems where Cook had focused on one.

His trouble was not mathematics but the state. Levin was politically suspect, entangled with the Soviet dissident scene, and his career was obstructed accordingly. His paper “Universal Search Problems” reached print only in 1973, years after the ideas were fully formed, in a Soviet journal, in Russian, at a length of two pages. For a long stretch neither man knew of the other; when the two lines of work met, the discovery was recognized as joint, and the theorem carries both names. Levin emigrated to the United States in 1978, took a second doctorate at MIT in 1979, and has taught at Boston University since 1980. He received the Knuth Prize in 2012 for the discovery of NP-completeness and for founding average-case complexity theory. The pairing is a clean natural experiment on how a scientific result can be delayed: same theorem, two systems, and the difference between prompt publication and a two-page article stalled for years was politics.

Why It Mattered So Fast

A theorem about the satisfiability of logic formulas could have stayed a curiosity. It did not, because Richard Karp at Berkeley saw immediately what it was for. In 1972 he published “Reducibility Among Combinatorial Problems”, showing that 21 well-known problems, from the traveling salesman to graph coloring to scheduling, are all NP-complete, all reducible to one another and to SAT. Overnight the abstraction had a body count. These were not artificial logic puzzles but the problems operations researchers and engineers had been failing to solve efficiently for decades. Karp’s list explained the failure: nobody had found fast algorithms for them because, if P is not NP, none exist, and a fast method for any one would break them all.

Cook received the 1982 Turing Award “for his advancement of our understanding of the complexity of computation”, the citation crediting the 1971 paper with founding the theory of NP-completeness. The concept the two of them defined is now the working tool by which computer scientists tell a hard problem from a merely tedious one. Faced with a new problem that resists fast solution, the first professional move is to try to prove it NP-complete: not a solution, but a certificate that no easy solution is likely, licensing the switch to approximations and heuristics. The million-dollar question of whether P equals NP remains open, and most researchers bet it does not, which would mean the wall Cook and Levin found is permanent.

📚 Sources