Skip to content

Richard Karp and the 21 Problems

Abstract

In 1971 Stephen Cook proved that one problem, Boolean satisfiability, was NP-complete. Richard Karp turned that isolated result into a map. In a talk at IBM’s Yorktown Heights laboratory in March 1972, “Reducibility Among Combinatorial Problems”, he showed that 21 problems that engineers and operations researchers had been failing to solve efficiently for decades, from the Hamiltonian circuit to graph coloring and the knapsack problem, were all equivalent in difficulty: each could be transformed into the others, so that all of them stand or fall together on the P versus NP question. Proving a new problem NP-complete became the standard first step in computer science when a problem resists a fast algorithm. Karp’s name is also on several algorithms every student learns (Held–Karp, Edmonds–Karp, Hopcroft–Karp, Rabin–Karp). He received the Turing Award in 1985, moved into computational biology in the 1990s and became the founding director of the Simons Institute for the Theory of Computing in 2012.

Richard Karp
Richard Karp giving a talk at EPFL in Lausanne, July 2009. Image: Rama, CC BY-SA 2.0 FR, via Wikimedia Commons.

From Harvard to IBM

Richard Manning Karp was born on 3 January 1935 in Boston. He took all three of his degrees at Harvard: a BA in 1955, an MA in 1956 and a PhD in applied mathematics in 1959, supervised by Anthony Oettinger, a pioneer of machine translation and computing at Harvard. Karp then spent the years from 1959 to 1968 at IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York, one of the places where the theory of algorithms was being built in the early 1960s.

At IBM he worked on combinatorial optimization, the mathematics of choosing the best among an enormous number of possibilities. With Michael Held he published in 1962 what is now called the Held–Karp algorithm, which solves the traveling salesman problem exactly by dynamic programming. It is exponential in the number of cities, but far faster than trying every tour, and more than sixty years later it is still the best known general exact bound for the problem.

In 1968 Karp moved to the University of California, Berkeley, as a professor of computer science, mathematics and operations research. Berkeley remained his base for the rest of his career, apart from four years at the University of Washington in Seattle in the late 1990s.

Algorithms with His Name

Karp’s name is attached to a series of standard algorithms:

  • Edmonds–Karp (published with Jack Edmonds in 1972, presented earlier) is a version of the Ford–Fulkerson method for maximum flow in a network that always augments along a shortest path, which guarantees a running time polynomial in the size of the network rather than in the size of the capacities.
  • Hopcroft–Karp (1973), with John Hopcroft (see Hopcroft and Tarjan), finds a maximum matching in a bipartite graph, for example assigning workers to jobs, faster than earlier methods by augmenting along many shortest paths at once.
  • Rabin–Karp (1987), with Michael Rabin, searches for a pattern in a text by comparing hash values that can be updated in constant time as the window slides along the text (see String Matching).

Edmonds’ 1965 paper “Paths, Trees, and Flowers” had argued that “polynomial time” was the right formal meaning of an efficient algorithm. Karp adopted that view and made it the organizing principle of his work.

Reducibility Among Combinatorial Problems

In 1971 Stephen Cook of the University of Toronto showed that satisfiability, the question of whether a Boolean formula can be made true, was in a precise sense the hardest problem in the class NP: any problem whose solutions can be checked quickly could be transformed into it (see Cook and Levin). Leonid Levin in Moscow proved similar results independently. Cook’s paper concerned logic and theorem proving, and few people outside a small community realized what it implied.

Karp read it as a technique. If an instance of problem A can be transformed in polynomial time into an instance of problem B with the same yes-or-no answer, then B is at least as hard as A. Chain such transformations outward from satisfiability and the hardness spreads to every problem reached.

From 20 to 22 March 1972 IBM held a symposium on the Complexity of Computer Computations at Yorktown Heights, organized by Raymond Miller and James Thatcher and attended by about 225 people. Karp presented “Reducibility Among Combinatorial Problems”. His list contained 21 problems, satisfiability and 0-1 integer programming among them, and showed that 19 problems beyond Cook’s were NP-complete, including clique, vertex cover, set cover, chromatic number, the directed and undirected Hamiltonian circuit, exact cover, subset sum and the knapsack problem, job sequencing and max cut. From the Hamiltonian circuit, the hardness of the traveling salesman problem followed at once. Most proofs were Karp’s own; a few he credited to Eugene Lawler, Robert Tarjan and “the Algorithms Seminar at Cornell.”

The paper appears to have been the first to use the notations P and NP, though it called the hardest problems “polynomial complete.” It also distinguished between a polynomial transformation, which maps one problem’s instances to the other’s, and a polynomial reduction, which may call a solver for the other problem many times; Cook had defined his results with the second but used only the first. The transformation, now usually called a many-one or Karp reduction, became the standard definition of NP-completeness.

The effect was to give one explanation to decades of separate failures. Operations researchers had spent years searching for fast algorithms for scheduling, routing, covering and packing problems, and blaming themselves when they found none. Karp’s list showed that the problems were in a precise sense the same problem in different forms. A fast algorithm for any of them would give fast algorithms for all of them, and if P does not equal NP, none exists.

Naming the Class

The name came later. In 1973 Donald Knuth, who needed a word for his books, wrote to experts in the field proposing “Herculean”, “formidable” or “arduous” for the class Cook and Karp had identified. The respondents disliked all three; several, including Michael Garey and David Johnson of Bell Labs, wrote in “NP-complete”. Knuth reported the outcome in SIGACT News in January 1974, “A Terminological Proposal”, and declared “NP-complete” the winner, with “NP-hard” for problems at least that hard but not necessarily in NP. Garey and Johnson’s Computers and Intractability (1979), a catalogue of several hundred NP-complete problems built on Karp’s method, became a standard reference, with more than 50,000 copies sold.

The Working Tool of Hardness

Karp’s paper changed what computer scientists do when a new problem resists solution. The first move is to try to prove it NP-complete. Success is a certificate rather than a solution: it says that an efficient exact algorithm is unlikely and that effort should go into approximation, heuristics, special cases or exponential algorithms that are fast enough in practice. That reflex, taught in every algorithms course, is Karp’s list turned into method. It also created the field of approximation algorithms, which asks how close to optimal a fast algorithm can get for a problem that cannot be solved exactly.

Karp himself spent the following years on what to do about hardness. He studied the probabilistic analysis of algorithms, showing that simple heuristics solve many NP-complete problems well on typical random inputs even if they fail in the worst case, and randomized algorithms, which use coin flips to run faster or more simply. With Richard Lipton he proved in 1980 the Karp–Lipton theorem, which links the question of whether NP problems have small circuits to the structure of the polynomial hierarchy. With Michael Luby he designed randomized approximation schemes for counting problems.

He 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.” His Turing lecture was titled “Combinatorics, Complexity, and Randomness.”

Biology and the Simons Institute

From the 1990s Karp turned to computational biology. The sequencing of genomes produced combinatorial problems of exactly the kind he had spent his career on: assembling sequences from fragments, building physical maps of chromosomes, finding patterns in gene expression data, comparing networks of interacting proteins. Many of them were NP-hard, and he and his students worked on algorithms that solved them well enough for real data. He was associated for many years with the International Computer Science Institute in Berkeley, where he led an algorithms group.

In 2012 he became the founding director of the Simons Institute for the Theory of Computing at Berkeley, funded by the Simons Foundation, which brings researchers together for semester-long programs on single topics. His doctoral students included Rajeev Motwani, Noam Nisan and Michael Luby. Besides the Turing Award he received the National Medal of Science (1996), the Benjamin Franklin Medal (2004) and the Kyoto Prize (2008).

📚 Sources