The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Richard Manning Karp

Born 3 January 1935, Boston, Massachusetts, USA

Turing Award (1985) “for his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.”

Richard Karp was born in Boston and graduated from Harvard University in Applied Mathematics (B.A. 1955, M.S. 1956, Ph.D. 1959). After his graduation, he went to the IBM Watson Research Center in Yorktown Heights, New York. From 1964 to 1965 he was a visiting associate professor of Electrical Engineering at the University of Michigan and then returned to IBM. From 1968, Karp was a professor of Computer Science and Industrial Engineering at the University of California, Berkeley. Between 1973 and 1975 he headed the Division of Computer Science. Richard Karp was from 1980 to 1994 a professor of Mathematics at Berkeley, and from 1995 to 1999 professor of Computer Science and adjunct professor of Molecular Biotechnology at the University of Washington. From 1988 to 1995 and from 1999 to 2012 he was a researcher at the International Computer Science Institute, which he co-founded. In 1999 he returned to Berkeley, where he works as University Professor of Computer Science, Mathematics, Industrial Engineering and Bioengineering to this day. The title of University Professor is a special award, which has been awarded only 38 times previously at Berkeley. Since 2012 he has been Director of the Simons Institute for the Theory of Computing in Berkeley.

Richard Manning Karp holds honorary doctorates from ten universities. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the recipient of numerous awards, including the U.S. National Medal of Science and the Kyoto Prize. During his teaching and research at Berkeley and Washington, Karp has supervised more than forty doctoral theses. In his spare time he is an avid reader and chess player.

There is a one million dollar prize for the answer to this question: does P = NP? But what is behind this question? Mathematical problems in the problem class P can be quickly solved. The P is the mathematical term for “quickly” and stands for polynomial. The running time of the fastest algorithms that solve the problem grows with the size of the problem at most as fast as a polynomial. NP, however, is the class of problems for which we can verify a given solution quickly. If the problem class P equaled the problem class NP, then one could find quickly solutions for all problems in NP – and if not, then the problems in NP are obviously “harder” than the problems in P.

But what problems are the hardest in NP? In 1971, Stephen Cook identified the first one: SAT, the problem of satisfiability of certain logical formulae. Cook and Karp also developed a mechanism by which one can build bridges between SAT and problems of another kind. The method is called “reduction”: one shows that one can efficiently translate problems in SAT into other problems in NP, which therefore are as hard as SAT. The bridges can even lead further: every problem that is connected with SAT in this way can by itself become the starting point for a new bridge to further problems.

Today there are thousands of problems known that are in this sense equivalent to SAT. The first 21 problems, classical bridgeheads of complexity theory, were discovered by Richard Karp and published in 1972 under the title “Reducibility Among Combinatorial Problems”. Moreover, Karp is known for a number of algorithms, including the famous Edmonds-Karp algorithm that determines the maximum flow in a network. [See Robert Endre Tarjan.]