Richard (Dick) Manning Karp

Co-publisher with John Hopcroft of the Hopcroft–Karp algorithm, still the fastest known method for finding maximum cardinality matchings in bipartite graphs, Karp is a computer scientist and computational theorist at the University of California, Berkeley, recognized for 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. He has also been awarded the National Medal of Science, and has been the recipient of the Harvey Prize of the Technion. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He has also been the recipient of several honorary degrees.

Born to Abraham and Rose Karp in Boston, Massachusetts, he had three younger siblings. Karp attended Boston Latin School before enrolling at 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 joined the research staff of the IBM Watson Research Center in Yorktown Heights, NY, where he worked until 1968. During that time, he did foundational work on models of parallel computation, which involves the simultaneous use of multiple coordinated computers to solve a single problem. Roughly twenty years later, he returned to the study of parallel computation and continued to work in that area.

In 1968, Karp became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a four-year period as a professor at the University of Washington, he remained at Berkeley. His dedication to teaching won him the UC Berkeley Distinguished Teaching Award in 1986. From 1988 to 1995, and from 1999 onward, he has also served as a Research Scientist at the International Computer Science Institute in Berkeley, where he led the Algorithms Group.

He made many important discoveries in computer science and operations research in the area of combinatorial algorithms. His major research interests have included bioinformatics, an interdisciplinary field that develops and improves upon methods for storing, retrieving, organizing, and analyzing biological data. In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the max-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 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, still 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. In 1987 he co-developed with Michael O. Rabin the Rabin–Karp string search algorithm, a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text.

During his years at Berkeley and Washington, Karp mentored almost forty Ph.D. students. In addition to his professional accomplishments, he is an avid reader and chess player.