Richard Manning Karp was born on January 3, 1935. He is an American computer scientist and computational theorist who works at the University of California, Berkeley. He is known for his research in the theory of algorithms. For this work, he received the 1985 ACM Turing Award, the Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

In 1992, Karp was elected to the National Academy of Engineering. He was recognized for his major contributions to the theory and application of NP-completeness, constructing efficient combinatorial algorithms, and applying probabilistic methods in computer science.

Biography

Richard Karp was born to Abraham and Rose Karp in Boston, Massachusetts. He has three younger siblings: Robert, David, and Carolyn. His family was Jewish, and he grew up in a small apartment in a neighborhood that was mostly Jewish at that time in Dorchester, Boston.

Both of his parents graduated from Harvard University. His mother earned her Harvard degree at age 57 by taking evening classes. His father wanted to go to medical school after Harvard but became a mathematics teacher because he could not afford the medical school fees. Karp 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 began working at IBM’s Thomas J. Watson Research Center.

In 1968, he became a 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. Except for 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.

Richard Karp was awarded the National Medal of Science. He received the Harvey Prize from the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his work on computational complexity. In 1994, he was elected a Fellow of the Association for Computing Machinery. He was also elected to the 2002 class of Fellows of the Institute for Operations Research and the Management Sciences. He has received several honorary degrees and is a member of the U.S. National Academy of Sciences, the American Academy of Arts and Sciences, and the American Philosophical Society.

In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the University of California, Berkeley.

Work

Karp has made many important discoveries in computer science, combinatorial algorithms, and operations research. His main current research interests are in bioinformatics.

In 1962, he worked with Michael Held to create the Held–Karp algorithm, a precise algorithm that takes a long time to solve problems related to the traveling salesman problem.

In 1971, he worked with Jack Edmonds to develop the Edmonds–Karp algorithm, which helps solve the maximum flow problem in networks. In 1972, he published an important paper titled "Reducibility Among Combinatorial Problems," where he showed that 21 problems are NP-complete.

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

In 1980, Karp and Richard J. Lipton proved the Karp–Lipton theorem. This theorem states that if SAT can be solved using Boolean circuits with a certain number of logic gates, then the polynomial hierarchy collapses to its second level.

In 1987, he worked with Michael O. Rabin to develop the Rabin–Karp string search algorithm.

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