# 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

- 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 462 home page

*cs462@descartes*

September 10 1997