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 and the Kyoto Prize in 2008.[1]
Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three
younger siblings: Robert, David, and Carolyn. 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. Richard Karp was awarded the National Medal of
Science, and was the recipient of the Harvey Prize of the Technion and
the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for
his insights into computational complexity. In 1994 he was inducted as
a Fellow of the Association for Computing Machinery. He is the
recipient of several honorary degrees.
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. In 1980, along with Richard J.
Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT
can be solved by Boolean circuits with a polynomial number of logic
gates, then the polynomial hierarchy collapses to its second level).
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 |
|
|