Richard M. Karp

Brief Biography

The oldest of four children and son of a junior high school teacher, Richard Manning Karp was born in Boston, Massachusetts. Karp attended Boston Latin School and developed an early interest in mathematics. He attended nearby Harvard University for his undergraduate education but  concluded that a career in pure mathematics was not for him. He decided to remain at Harvard and pursue graduate study. Starting in 1955, Karp began working at the university’s computation lab, spending productive summers with the Massachusetts Institute of Technology’s Lincoln Laboratory and General Electric. He wrote his dissertation on the analysis of programs with graph theory algorithms under Anthony G. Oettinger. After receiving his PhD, Karp joined the staff at IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York.  

At IBM, Karp was assigned to work on algorithms for logic circuit design. As the field of combinatorial algorithms grew, the company hired Alan Hoffman to head a combinatorics research group. Hoffman became a mentor for Karp whose work was starting to include the design parallel computation models.

Interested in teaching, Karp moved to the University of California, Berkeley in 1968. He saw the move to Berkeley as the end of his “scientific apprenticeship.” As a professor, Karp never set a thesis problem for his students and instead worked closely with each individual to develop a direction that best fit their interests and talents. In 1971, he read a paper by Steve Cook on the proposition satisfiability problem. This inspired Karp to develop the notion of NP-completeness, which successfully placed computational complexity theory in touch with real world applications. In 1972, he and Jack Edmonds devised the Edmonds-Karp algorithm, an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network.

Karp’s algorithmic work has had a significant influence on operations research. His 1977 paper on a probabilistic analysis of portioning algorithms for the travelling-salesman problem was recognized as “the first major application of probabilistic analysis to a combinatorial optimization problem” and was awarded the Frederick W. Lanchester Prize. Karp’s contributions show that traditional combinatorial optimizations problems are equally difficult in the sense that there is an efficient algorithm for solving any single problem if and only if there are efficient algorithms for solving all of them. In 1990, he was awarded the John von Neumann Theory Prize for his seminal developments in computational theory and algorithms in operations research and the management sciences.

In addition to his theory-driven work, Karp has contributed computational molecular biology. Starting in the early 1990s, he began to seriously think about the application of his algorithmic knowledge to biology and medicine. Karp joined University of Washington in 1994 as an Adjunct Professor of Molecular Biology to further explore this subject. He developed an interest in the computational mapping of the human genome. As Karp worked more with real world applications, he began to criticize the theory community for focusing on “artificial problems” and being “ingrown.”

In addition to the Lanchester and von Neumann Prizes, Karp has received a number of additional accolades including the National Medal of Science. In 1985 he won the Alan M. Turing Award, one of the highest honors a computer scientist can receive. 

Other Biographies

Wikipedia Entry for Richard M. Karp

Parallel Computing Research Newsletter. Parallel Computer Pioneers - Richard M. Karp. Accessed April 30, 2015. (link)

University of California, Berkeley Electrical Engineering & Computer Sciences. Faculty: Richard M. Karp. Accessed April 30, 2015. (link) 

Klarreich, E (2013) Science Lives: Richard Karp. Accessed October 4, 2018 (link)

Simons Foundation. Science Lives: Richard Karp.  Interviewed by Christos Papadimitriou. Published December 13, 2013. Accessed May 11, 2015. (video)