Richard M. Karp

Richard M. Karp is an American computer scientist whose work shaped algorithms, computational complexity, and combinatorial optimization. He is especially known for establishing the NP-completeness of 21 fundamental problems.

Connect

Karp's 21 NP-complete problems: A 1972 collection of 21 combinatorial problems shown to be NP-complete through polynomial-time reductions. This paper established the breadth of NP-completeness across familiar optimization and decision problems.
Maximum flow problem: The problem of finding the greatest possible flow from a source to a sink in a capacitated network. Karp developed influential algorithms for network flow and related combinatorial optimization.
Jack Edmonds: A mathematician and computer scientist whose work on matching and optimization shaped combinatorial optimization. Edmonds collaborated with Karp on algorithms, including a widely used maximum-flow method.
Harvard University: A private research university in Cambridge, Massachusetts, founded in 1636. Karp earned his undergraduate, master’s, and doctoral degrees there.
NP-completeness: The study of decision problems to which every problem in NP can be reduced in polynomial time. Karp’s results helped turn this complexity classification into a central tool.
Edmonds-Karp algorithm: A maximum-flow algorithm that repeatedly augments flow along shortest residual paths and runs in polynomial time. Its name records Karp’s collaboration with Jack Edmonds on a practical flow method.
Stephen Cook: A computer scientist who proved that Boolean satisfiability is NP-complete. Cook’s theorem gave Karp the foundational result from which his reductions proceeded.
University of California, Berkeley: A public research university in Berkeley, California, founded in 1868. Karp joined Berkeley’s faculty and spent much of his academic career there.
Cook-Levin theorem: The theorem that Boolean satisfiability is NP-complete. It supplied the starting point for the reduction chain behind Karp’s list.
Bipartite matching: The problem of selecting disjoint edges in a bipartite graph to maximize the number of matched vertices. Matching is a central combinatorial problem connected to Karp’s algorithmic work.