Richard M. Karp

Richard Manning Karp
Richard Manning Karp
	Karp in 2009
Born	January 3, 1935; Boston, Massachusetts, US
Education	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	Mathematics; Computer science
Institutions	University of California, Berkeley; IBM
Thesis	Some applications of logical syntax to digital computer programming (1959)
Doctoral advisor	Anthony Oettinger
Doctoral students	Faith Ellen; Sally Floyd; Phillip Gibbons; Dan Gusfield; Narendra Karmarkar; Valerie King; Michael Luby; Rajeev Motwani; Noam Nisan; Raymond Reiter; Eunice Santos; Thomas J. Schaefer; Ron Shamir; Barbara Simons; Eric Xing; Norman Zadeh;

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 the 1985 ACM Turing Award, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

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.