Richard M. Karp is a professor emeritus in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley, with further appointments in mathematics, bioengineering, and operations research. His own Berkeley faculty page records the milestone that made his name: in 1972 he published “Reducibility Among Combinatorial Problems,” in which he proved 21 problems to be NP-complete.
Karp’s contribution built directly on Stephen Cook’s 1971 result that the satisfiability problem is NP-complete. Where Cook established that a single problem was NP-complete, Karp showed by a web of polynomial-time reductions that a long list of well-known combinatorial problems, from the traveling salesman tour to graph coloring to the knapsack problem, were all NP-complete too. The 1972 paper hosted by the University of Maryland sets out these reductions and the now-standard method of proving a new problem NP-complete by reducing a known one to it.
That methodology turned NP-completeness from a single curiosity into a practical diagnostic that programmers and researchers still use: if you can reduce a known NP-complete problem to yours, you have strong evidence that no efficient algorithm is likely to exist. The 21 problems gave the field a starter set of “hard” problems to reduce from.
His faculty page lists the 1985 ACM A.M. Turing Award among his honors, awarded for his continuing contributions to the theory of algorithms, most notably to the theory of NP-completeness, alongside the U.S. National Medal of Science and many other prizes. In later years his research turned toward algorithmic methods in genomics and computer networking.