Richard ("Dick") Manning Karp

Richard Karp was born in Boston, Massachusetts on January 3, 1935. He attended Boston Latin School, and received the A.B, S.M. and Ph.D. degrees in Mathematics and Applied Mathematics from Harvard University in 1955, 1956 and 1959.

Karp then joined the research staff of the IBM Watson Research Center in Yorktown Heights, NY, where he worked until 1968. During that time, Karp did foundational work on models of parallel computation, which involves the simultaneous use of multiple coordinated computers to solve a single problem. Roughly twenty years later, he returned to the study of parallel computation and continues to work in that area.

Motivated by the desire to teach and "to be where the action is," in 1968 Karp moved to the University of California, Berkeley, with appointments in Computer Science and in Operations Research. His dedication to teaching won him the UC Berkeley Distinguished Teaching Award in 1986.

Karp's initial research at Berkeley focused on heuristic algorithms for hard combinatorial problems, particularly for the notoriously difficult Traveling Salesmen Problem (TSP). Like many combinatorial problems, there was no efficient TSP algorithm that could be proved correct for all input, and whose worst-case running time is bounded by a polynomial function of the input size. Also lacking was an explanation of why an efficient algorithm had been so elusive.

In one of the most significant paper of his career, Karp's 1972 Reducibility Among Combinatorial Problems provided a convincing explanation for the elusiveness of an efficient solution. In that seminal paper, Karp expanded on the concept (first introduced by Stephen Cook in 1971, and independently by Leonid Levin) of NP-completeness and proved that if any of twenty-one well-known difficult problems (including TSP) could be solved by an efficient algorithm, then all of the problems could be efficiently solved.  NP-completeness shows, in an important sense, that these 21 problems are all equivalent. The collective failure by many talented people to find efficient algorithms for specific NP-complete problems strongly suggests that no efficient algorithm exists for any of them. Importantly, the paper established a framework for adding additional problems to the class of NP-complete problems, which has since grown to include many thousands. Today, only one or two classic combinatorial problems remain unclassified as to whether they are NP-complete or not. While most of the classified classic problems are NP-complete, several have been shown to be efficiently solvable.

Karp's work on NP-completeness substantially motivated the discussion  of the famous unsolved P = NP question and its further examination by mathematicians and computer scientists. In essence, P = NP asks whether finding a solution to a problem is inherently more difficult than verifying that a proposed solution is correct. Not only is the problem considered the most important open question in theoretical computer science, it is also one of the most important open questions in mathematics.

The year after his paper on NP-completeness, Karp co-authored with Jack Edmonds and John Hopcroft (himself a Turing Award recipient) two very significant papers on efficient algorithms for network flow and bipartite graph matching. The network flow problem is to compute the maximum steady-state amount of material (for example, liquids in a pipe or bits in a communication network) that can be transported from a source to a destination in a network, where each edge (pipe, wire, road etc.) in the network can have a different but bounded capacity. This is one of the most widely studied problems in optimization and algorithmic computer science, and is not limited to physical networks as the same problems arise in, for example, biological cycles. The bipartite matching problem is a particularly useful special case of network flow that has a huge number of non-physical applications. Karp and Hopcroft showed in 1973 that the bipartite matching problem can be solved more efficiently than the general network flow problem [4] .

Another major theme in Karp's research has been the use of probability in both the design and analysis of efficient algorithms. Karp's interest in the probabilistic analysis of algorithms began in the 1980s, when he examined questions of the average, rather than the worst-case, running times of particular algorithms. In probabilistic analysis, the algorithm is fixed and deterministic, but its input is assumed to be drawn from a space universe of possible inputs according to a well-specified probabilistic model. The analysis finds the expected running time (or other characteristic) for that distribution of inputs. Karp later became active in the design of randomized algorithms, where the algorithm itself, rather than the input to the algorithm, has a random component. Surprisingly, randomizing the behavior of an algorithm can often significantly reduce its expected running time for any input.

Karp's most recent research has been in computational biology. This work began in the 1990s, as the field began to grow rapidly under the influence of the Human Genome Project. Karp first examined physical mapping of genes, devising algorithms to help determine the physical location of genes in a genome given the limited indirect experimental information about gene location. Such algorithms were especially important before affordable full DNA sequencing became available. From that beginning, Karp has examined a wide range of algorithmic issues in biology, such as:

1. determining protein interactions
2. designing and analyzing methods for gene mapping under different data collection technologies
3. designing and analyzing methods for problems that arise in population genetics and family pedigree analysis
4. finding repeating patterns and structures in gene sequences
5. constructing and analyzing networks that represent biological interactions, such as protein-protein contact, gene regulation, and metabolic pathways.

Much of Karp's work in computational biology uses techniques from combinatorial optimization, but more recently his work has also involved stochastic approaches from the field of machine learning. A new direction for Karp, this recent work on machine learning is related to his continuing interest in the use of probability in the design of algorithms and in the analysis of algorithmic behavior.

In 1995 Karp left Berkeley for the Department of Computer Science at the University of Washington, where he was also an Adjunct Professor of Molecular Biotechnology. He returned to Berkeley in 1999 with appointments in Computer Science, Mathematics, and Bioengineering.

In addition, Karp is a Senior Research Scientist at the International Computer Science Institute in Berkeley, and was a principal in the creation of the Institute. Karp is currently a University Professor at the University of California, a prestigious title that has been awarded only thirty-eight times. Other major awards include election to the National Academy of Sciences in 1980, election to the National Academy of Engineering in 1992, the U.S. National Medal of Science in 1996, and the Kyoto Prize in 2008.

During his years at Berkeley and Washington, Karp mentored almost forty Ph.D. students. In addition to his professional accomplishments, Karp is an avid reader and chess player.

B. Simons and D. Gusfield