Richard M. Karp

Richard Manning Karp, born on 3 January 1935 in Boston, Massachusetts, is an American computer scientist and computational theorist at the University of California, Berkeley, best known for his research in the theory of algorithms. He took his bachelor's degree at Harvard in 1955, a master's in 1956 and a doctorate in applied mathematics in 1959, then worked at IBM's Thomas J. Watson Research Center before becoming a professor of computer science, mathematics and operations research at Berkeley in 1968. In 1972 he published the landmark paper "Reducibility Among Combinatorial Problems", proving twenty-one problems NP-complete and setting the standard method for showing that problems are computationally hard. His name is attached to the Held-Karp algorithm for the travelling salesman problem, the Edmonds-Karp algorithm for maximum flow, the Hopcroft-Karp matching algorithm, the Rabin-Karp string search and the Karp-Lipton theorem on the polynomial hierarchy. He received the 1985 ACM Turing Award, the National Medal of Science, the Benjamin Franklin Medal in 2004 and the Kyoto Prize in 2008, and in 2012 became founding director of the Simons Institute for the Theory of Computing.