CN / EN
Richard Karp
  • 1985 Turing Award

Intro

1985 Turing Award
Richard Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985.

Education and Work Experience

1959, Ph.D., Applied Mathematics, University of Harvard
1959-1968, Researcher at IBM's Thomas J. Watson Research Center
1968-Present, Professor of Computer Science, Mathematics, and Operations Research at the UC Berkeley

Honors and Awards

1980, Member of the United States National Academy of Sciences
1985, Turing Award
1992, Member of the United States National Academy of Engineering
1994, Fellow of Association for Computing Machinery

Major Academic Achievements

Karp has made many important discoveries in computer science, combinatorial algorithms, and operations research. His major current research interests include bioinformatics. In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in bipartite graphs. 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).