Richard Karp

Life and career

Stephen Cook proved in 1971 that satisfiability is NP-complete. It was a beautiful result and it might have remained a curiosity about one artificial-looking problem in logic. What made it the organizing fact of theoretical computer science was a paper Richard Karp published the following year, "Reducibility Among Combinatorial Problems," which took twenty-one problems people actually cared about — the traveling salesman, graph coloring, set cover, knapsack, clique, vertex cover, Hamiltonian circuit, integer programming — and showed by explicit reduction that all of them are NP-complete, and therefore all equivalent to each other and to SAT. Overnight, a large and previously disorganized collection of frustrations turned out to be one frustration wearing different hats.

Karp was born in Boston in 1935, the eldest of four children in a family where, by his account, education was the assumed path out. He went to Boston Latin School and then to Harvard, where he took his AB in 1955, his master's in 1956, and his PhD in applied mathematics in 1959. Computer science did not exist as a department; he worked in the Harvard Computation Laboratory, which is how a mathematician of that era ended up in computing.

He spent nine years at IBM's Thomas J. Watson Research Center in Yorktown Heights (1959–1968), which was then one of the few places on earth where one could work on algorithms as a research subject. It was there, with Michael Held, that he developed the Held–Karp dynamic programming algorithm for the traveling salesman problem — still the best known exact algorithm's basic approach — and the Held–Karp lower bound, which underlies practical TSP solvers.

In 1968 he moved to Berkeley, where he has spent essentially the rest of his career, in a joint appointment spanning computer science, mathematics, and operations research, with an interval at the University of Washington in the mid-1990s before returning. He was a founding figure at the International Computer Science Institute in Berkeley and led its algorithms group. Colleagues describe an unusually generous and lucid teacher — the kind of theorist whose talks are followed by the whole room rather than a third of it — and his doctoral students include a substantial fraction of the algorithms community.

His later work moved into computational biology, where he applied combinatorial and probabilistic algorithms to genome assembly, physical mapping, and the analysis of expression data. He received the Turing Award in 1985, the National Medal of Science in 1996, the Kyoto Prize in 2008, and holds memberships in the National Academies of Sciences and Engineering. Berkeley students still take his courses' descendants; the reduction technique he made routine is now taught in the first algorithms class anyone takes.

Key contributions

**The 21 NP-complete problems (1972).** The technical device is polynomial-time many-one reduction: problem *A* reduces to problem *B* if any instance of *A* can be transformed, in polynomial time, into an instance of *B* with the same yes/no answer. If *A* is known hard and *A* ≤ₚ *B*, then *B* is hard too. Karp organized his twenty-one problems into a reduction tree rooted at SAT, so each new result required only one new transformation. The reductions themselves are small acts of ingenuity — encoding a clause as a triangle in a graph, an assignment as a vertex cover — and the paper reads like a tour of them.

The intellectual payoff is threefold. It established **NP-completeness as a practical diagnostic**: a researcher stuck on an optimization problem could check whether it was in the class, and if so, stop looking for an exact polynomial algorithm and start looking for approximations, heuristics, or tractable special cases. It made **P vs NP** the central open question of the field, by showing the class contained everything anyone cared about rather than one contrived problem. And it introduced the *style* of complexity theory — classify problems by reduction into equivalence classes — that structures the subject to this day. Garey and Johnson's 1979 catalog of hundreds of NP-complete problems is Karp's method industrialized.

**Edmonds–Karp (1972, with Jack Edmonds).** The Ford–Fulkerson max-flow method's running time depends on the augmenting paths chosen and can be terrible or even non-terminating with irrational capacities. Edmonds and Karp showed that always choosing a *shortest* augmenting path (breadth-first) bounds the number of augmentations by *O*(*VE*), giving *O*(*VE*²) overall — independent of the capacity values. This is one of the first results establishing that the *choice rule* inside a method determines whether it is an algorithm in the strong sense. The same paper's framing of flows and cuts is the basis for the enormous applied reach of max-flow/min-cut, which in machine learning shows up as graph cuts for MAP inference in binary MRFs.

**Hopcroft–Karp (1973).** Maximum bipartite matching in *O*(*E*√*V*) by finding maximal sets of vertex-disjoint shortest augmenting paths in phases. Matching is the algorithmic backbone of assignment problems, and this remained the fastest known combinatorial algorithm for the problem for decades.

**Rabin–Karp (1987, with Michael Rabin).** String matching by rolling hash: compute a hash of the pattern and of each window of the text, compare hashes, verify on collision. It is randomized, average-case linear, and it generalizes gracefully to searching for many patterns at once — the basic technique behind plagiarism detection and much of practical text indexing.

**Randomized and approximation algorithms.** Karp was central to establishing randomization as a legitimate algorithmic resource and to the theory of approximation — proving both what can be approximated within a factor and, later with others, where hardness of approximation begins. The **Karp–Lipton theorem** (1980) shows that if SAT has polynomial-size circuits, the polynomial hierarchy collapses to its second level, one of the foundational results connecting non-uniform and uniform complexity. He also did influential work on probabilistic analysis of algorithms — asking not "what is the worst case" but "what happens on random instances," which turns out to be the right question for many problems that are NP-hard but routinely solved in practice.

In battle

Karp is, by the numbers, one of the strongest cards in the game: mean 49.0 across 101 problems, median 45, seventeen dominant scores, twenty-four at 70 or above, and only fifteen problems at or below 20. Almost nobody else combines that peak count with that little downside. The reason is structural and rather elegant: his central contribution is a *web of equivalences*, so any problem that reduces into it is his problem.

His top score is **Frequencies without interference** (P269) at 97 — frequency assignment, which is graph coloring, which is on his list of twenty-one. Transmitters are vertices, interference is edges, channels are colors, and minimum channels is the chromatic number. He formalized it and also worked on the approximation side, so he can both prove the instance hard and certify a good-enough bound. **Is there a fast route through every city?** (P031) at 96 is TSP, which he attacked from both directions — Held–Karp exact dynamic programming and the NP-completeness classification. **The assignment in the sky** (P043) at 94 is crew scheduling as an assignment/set-partitioning problem, where Hopcroft–Karp matching and integer programming both apply. **The problem all others reduce to** (P158) at 92 is the Cook–Levin/NP-completeness scenario itself, and he sits just below the theorem's authors for the excellent reason that Cook proved it — Karp made it matter. **The variables that must be whole** (P178) at 90 is integer programming, on his list. **Solve the impossible formula** (P187) at 90 is SAT solving. **The exchange with no prices** (P206) at 90 is matching markets. **How much can the railway carry?** (P267) at 90 is max-flow, which is Edmonds–Karp.

His category means make the shape obvious: `computability` 62.1, `networks` 59.5, `search` 59.0, `optimization` 57.8, all across fifteen or sixteen problems each — sustained strength, not a single peak. `games` at 49.0 across thirteen reflects that game-theoretic computation is largely a complexity question.

His losses fall in exactly one place: continuous statistics and modern empirical machine learning. He scores 13 on **The posterior at web scale** (P213), 10 on **Attention replaces recurrence** (P088), 10 on **The agent that games its reward** (P225, reward hacking), 8 on **Words from waveforms** (P073), 6 on **When the predictors move together** (P134, multicollinearity), and 6 on **The coefficient that flips sign** (P143). His `regression` mean is 6.0, `perception` 11.5, `nlp` 12.5, `small-sample` 15.5.

There is a subtlety here worth flagging for students, because it is easy to over-read the losses. Karp is not statistically illiterate — he worked on probabilistic analysis of algorithms and on computational biology with real data, and his `testing` (29.0), `experimental-design` (28.5), and `classification` (25.5) means are respectable by theory-cohort standards. What he lacks is the *estimation* tradition: nothing in his work concerns fitting parameters to noisy observations, quantifying uncertainty about a coefficient, or reasoning about confounding. Complexity theory asks whether a problem can be solved; statistics asks how confident you should be in an answer. Those questions barely touch.

Play Karp anywhere there is a combinatorial structure to be analyzed, a scheduling or assignment or routing problem, or a question about whether something is tractable at all — he is close to the best answer available on all of it. Play him against a regression and he is a Turing Award winner with nothing to say.