Richard Manning Karp | |
|---|---|
 Richard Karp at the EPFL in 2009 | |
| Born | January 3, 1935 |
| Nationality | American |
| Alma mater | Harvard University (BA, MA, PhD) |
| Known for | Aanderaa–Karp–Rosenberg conjecture Edmonds–Karp algorithm Held–Karp algorithm Hopcroft–Karp algorithm Karmarkar–Karp algorithm Rabin–Karp string search algorithm Karp–Lipton theorem Karp's 21 NP-complete problems Vector addition system |
| Awards | Fulkerson Prize (1979) Turing Award (1985) John von Neumann Theory Prize (1990) IEEE Computer Society Charles Babbage Award (1995) National Medal of Science (1996) Harvey Prize (1998) EATCS award (2000) Benjamin Franklin Medal (2004) Kyoto Prize (2008) |
| Scientific career | |
| Fields | Computer Science |
| Institutions | University of California, Berkeley IBM |
| Thesis | Some Applications of Logical Syntax to Digital Computer Programming (1959) |
| Doctoral advisor | Anthony Oettinger[1] |
| Doctoral students | |
Richard Manning Karp (born January 3, 1935) 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, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.[2]
Karp was elected a member of the National Academy of Engineering (1992) for major contributions to the theory and application of NP-completeness, constructing efficient combinatorial algorithms, and applying probabilistic methods in computer science.