Richard Karp
From Wikipedia, the free encyclopedia
Richard Manning Karp (born 1935) is a computer scientist and computational theorist, 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, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete. 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.
Preceded by John McCarthy |
Benjamin Franklin Medal in Computer and Cognitive Science 2004 |
Succeeded by Aravind Joshi |
[edit] External links
- ACM Crossroads magazine interview/bio of Richard Karp
- Karp's Home Page at Berkeley
- American Mathematical Society Genealogy for Richard Karp
Categories: 1935 births | Living people | Computer pioneers | Jewish scientists | American computer scientists | American mathematicians | Turing Award laureates | John von Neumann Theory Prize winners | National Medal of Science recipients | University of California, Berkeley faculty | Members and associates of the US National Academy of Sciences | Erdős number 2