Richard M. Karp

In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the University of California, 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 was elected to the 2002 class of Fellows of the Institute for Operations Research and the Management Sciences. He is the recipient of several honorary degrees and a member of the U.S. National Academy of Sciences, the American Academy of Arts and Sciences, and the American Philosophical Society.

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.

In 1987 he co-developed with Michael O. Rabin the Rabin–Karp string search algorithm.

His citation for the (1985) Turing Award was as follows:

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).

In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in bipartite graphs.

In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the maximum 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 1968, he became professor of computer science, mathematics, and operations research at the University of California, Berkeley. Karp was the first associate chair of the Computer Science Division within the Department of Electrical Engineering and Computer Science. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a research scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group.

In 1962 he co-developed with Michael Held the Held–Karp algorithm, an exact exponential-time algorithm for the travelling salesman problem.

Both his parents were Harvard graduates (his mother eventually obtaining her Harvard degree at age 57 after taking evening courses), while his father had had ambitions to go to medical school after Harvard, but became a mathematics teacher as he could not afford the medical school fees. 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 started working at IBM's Thomas J. Watson Research Center.

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.