Richard Karp and the 21 Problems
Abstract
In 1971 Stephen Cook proved that one problem, Boolean satisfiability, was NP-complete. It could have remained an isolated technical result. Richard Karp turned it into a map of the whole territory. His 1972 paper took 21 famous problems that engineers and operations researchers had been failing to solve efficiently for decades, from the traveling salesman to graph coloring to bin packing, and proved them all NP-complete: all equivalent, all reducible to one another, all standing or falling together on the P versus NP question. Karp gave the field its central diagnostic tool and won the 1985 Turing Award for it.
From IBM to Berkeley
Richard Karp was born in Boston in 1935, the son of Jewish parents, and took all three of his degrees at Harvard, finishing a doctorate in applied mathematics in 1959. He began at IBM’s Thomas J. Watson Research Center, where much of the early theory of algorithms was being built, and moved to the University of California, Berkeley, in 1968. Berkeley was where he stayed, and where in 2012 he became founding director of the Simons Institute for the Theory of Computing.
Karp’s fingerprints are on a striking number of the algorithms students still learn by name. The Held-Karp algorithm (1962) solves the traveling salesman problem by dynamic programming. The Edmonds-Karp algorithm (1971) put a predictable time bound on network flow. The Hopcroft-Karp algorithm (1973) matches bipartite graphs efficiently. The Rabin-Karp algorithm (1987) searches strings using hashing, a fixture of the string-matching canon. Any one of these would anchor a normal career. None is the reason he has a Turing Award.
Reducibility Among Combinatorial Problems
The 1971 Cook-Levin theorem proved that satisfiability was NP-complete: hard, and universal, in the sense that every problem in NP reduces to it. Read narrowly, this said something about logic formulas. Karp read it as a technique. If you can transform problem A into problem B in polynomial time such that a solution to B gives a solution to A, then B is at least as hard as A. Chain these reductions and you can spread the label of “as hard as SAT” across the whole landscape.
In 1972 he did exactly that, in a paper titled “Reducibility Among Combinatorial Problems”. He took 21 problems, all long-studied, all resistant to efficient solution, and proved each of them NP-complete by reduction: the traveling salesman, the Hamiltonian circuit, graph coloring (the chromatic number), the clique problem, vertex cover, set cover, the knapsack problem, job scheduling, and more. The effect was to unify decades of separate frustrations into a single explanation. Operations researchers had spent years failing to find fast algorithms for these problems and blaming their own cleverness. Karp’s list reframed the failure as structure. Nobody had found a fast algorithm for any of them because they are all the same problem in disguise, and if P is not NP, no fast algorithm for any of them exists. He also formalized the polynomial-time many-one reduction that remains the standard definition tool of NP-completeness.
The Working Tool of Hardness
The paper changed how computer scientists approach a new problem. Confronted with something that resists fast solution, the professional first move is to try to prove it NP-complete. Success is not a solution; it is a certificate, a proof that no efficient algorithm is likely to exist and that effort should shift to approximation, heuristics, or special cases. This diagnostic reflex, taught in every algorithms course, is Karp’s list turned into a habit. The list also seeded the entire industry of approximation algorithms, since a problem you cannot solve exactly and fast you may still solve nearly and fast.
Karp received the 1985 ACM Turing Award “for his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness.” He later added the National Medal of Science, the Benjamin Franklin Medal (2004), and the Kyoto Prize (2008). His work also reached beyond pure theory: in later decades he applied algorithmic thinking to computational biology and the analysis of large-scale data. The unifying thread across the network-flow algorithms, the string search, and the 21 problems is a single conviction, that the right way to understand a computation is to ask precisely how its cost grows, and to treat “polynomial time” as the boundary of the possible.