Richard Karp

Richard Manning Karp was born in Boston, Massachusetts on January 3, 1935. He attended Harvard University where he received his AB in 1955, his SM in 1956, and his Ph.D. in 1959. From 1959 to 1968 he was on the research staff at the IBM Watson Research Center in Yorktown Heights, NY. In 1968 he joined the faculty at the University of California, Berkeley, where he taught until 1996. Since 1996 he has taught at the University of Washington in Seattle.

Karp was among the first to recognize the importance of Stephen Cook's concept of NP-completeness. Building on Cook's work, in a very influential and groundbreaking 1972 paper, Karp showed the NP-completeness of 21 fundamental problems whose computational complexity had been open for years, including the problems CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE (both directed and undirected verisons), 3-DIMENSIONAL MATCHING, KNAPSACK, and PARTITION.

Since then, Karp has made many fundamental contributions to theoretical computer science, including work on fast parallel algorithms, string matching, and, most recently, computational biology.

Karp has won many awards for his research, including the Fulkerson Prize in Discrete Mathematics, 1979; the Lanchester Prize in Operations Research, 1977; the ACM Turing Award in 1985; and the US National Medal of Science, 1996.

Sources

  1. R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher, eds., Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85-103.
Back to Theory of Computing Hall of Fame Main Page
Back to CS 360 home page