Richard Karp
Richard Manning Karp (born
1935) is a
computer scientist, notable for research in the
theory of algorithms, for which he received a
Turing Award in
1985.
Karp was born in
Boston, Massachusetts. He attended
Harvard University, where he received his
Bachelor's degree in
1955, his
Master's degree in
1956, and his
Ph.D. in
applied mathematics in
1959. He then worked at
IBM's
Thomas J. Watson Research Center. In
1968, he became Professor of Computer Science, Mathematics, and Operations Research at the
University of California, Berkeley. Apart from a 4-year period as a professor at the
University of Washington, he has remained at Berkeley. Karp was also the recipient of the 2004
Benjamin Franklin Medal in Computer and Cognitive Science for his insights into
computational complexity.
His citation for the Turing Award was as follows:
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. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.In
1971 he co-developed with
Jack Edmonds the
Edmonds-Karp algorithm for solving the max-flow problem on networks.In
1987 he co-developed with
Michael O. Rabin the
Rabin-Karp string search algorithm.
He has made many other important discoveries in computer science and
operations research in the area of
combinatorial algorithms. His major current research interests include
bioinformatics.
*
ACM Crossroads magazine interview/bio of Richard Karp*
Karp's Home Page at Berkeley
