In 1972, Richard Manning Karp did just that. His work transformed computer science from a collection of clever tricks into a discipline with deep structure — revealing why some problems stubbornly resist all efficient solutions.
Profile: A Mathematician Turned Architect of Complexity
Richard M. Karp was born in 1935 in Boston, Massachusetts. He showed early brilliance in mathematics, earning his bachelor’s, master’s, and Ph.D. from Harvard University, completing the latter in 1959 under mathematician Ivan Niven.
After joining IBM’s Thomas J. Watson Research Center, Karp became fascinated by the emerging field of theoretical computer science. Later, at the University of California, Berkeley, he built one of the world’s most influential schools of thought in algorithms and computational complexity.
Over his long career, he has held key positions at UC Berkeley, the University of Washington, and several research institutes. His honors include the Turing Award (1985), the National Medal of Science (1996), and membership in both the National Academy of Sciences and the American Philosophical Society.
But beyond accolades, Karp’s enduring contribution is a conceptual framework — a way of understanding why some computational problems are inherently difficult.
The 1972 Paper: “Reducibility Among Combinatorial Problems”
Karp’s 1972 paper in Complexity of Computer Computations is one of the foundational texts of theoretical computer science. Building upon Stephen Cook’s 1971 result — the Cook Theorem, which proved that the Boolean satisfiability problem (SAT) is NP-complete — Karp took the next monumental step: connecting theory to reality.
Where Cook’s work was a spark, Karp’s was the fire that spread.
The Idea: Reductions and the Web of Hardness
Karp introduced a systematic method for proving that diverse, seemingly unrelated problems are all computationally equivalent in difficulty.
He used polynomial-time reductions — efficient transformations that show how solving one problem could be used to solve another.
If problem A can be reduced to problem B efficiently, and A is already known to be NP-complete, then B must be NP-complete too. This logical chain turned out to be a powerful tool for mapping complexity across the entire computational universe.
The 21 NP-Complete Problems
In this paper, Karp identified 21 fundamental problems from across mathematics, logic, and computer science, and proved each to be NP-complete by reduction from SAT.
These include:
・The Traveling Salesman Problem (TSP) — finding the shortest route visiting each city once.
・Graph Coloring — coloring vertices so that no two adjacent ones share a color, using as few colors as possible.
・The Knapsack Problem — selecting items with given weights and values to maximize value under a weight limit.
・Hamiltonian Cycle, Vertex Cover, Subset Sum, and many others.
This list was not just academic bookkeeping — it revealed that practical optimization problems in logistics, design, and scheduling were all reflections of the same deep computational structure.
The Legacy: A Theory of Limits
Karp’s work solidified the concept of NP-completeness as a cornerstone of computer science. It unified hundreds of seemingly unrelated problems under a single theoretical umbrella — and, perhaps more importantly, defined the boundaries of algorithmic possibility.
Because of Karp, we now understand that if any one NP-complete problem can be solved efficiently (in polynomial time), then all of them can — and the long-standing question P = NP? would finally be answered.
That question remains one of the greatest open problems in mathematics.
Karp’s influence extends far beyond complexity theory. His later research spanned randomized algorithms, graph theory, network flows, and computational biology. Yet the spirit of his 1972 insight — that structure emerges when you look for deep equivalences — runs through all his work.
The Broader View
Karp’s genius lies not only in what he proved, but in how he thought.
He showed that the world’s messy puzzles — from routing trucks to sequencing genes — can be understood as instances of elegant mathematical universals. He taught us that “hardness” itself can be studied, classified, and sometimes even tamed.
In that sense, Richard Karp didn’t just solve problems. He explained why some problems refuse to be solved — and turned that refusal into a theory.
here’s a reading + YouTube list for Richard M. Karp (nerd-style) that you can use to deepen your understanding of his work and its context. You can pick and choose based on how deep you want to dive.
YouTube & Lecture Videos
Here are videos featuring Richard Karp (or about his topics) — good for hearing his voice (literally) and getting visual/lecture-style context.
NP‑Complete Problems, lecture by Richard Karp
— A direct lecture where he tackles how to distinguish “easy” vs “hard” combinatorial/search problems.
-
“NP-Completeness | Richard Karp and Lex Fridman” — a more informal interview/discussion format. (YouTube)
-
“Karp on the definition of P and NP.” — He explains how he sees the classes P and NP, in his own words. (YouTube)
-
“Richard M. Karp Distinguished Lectures” playlist — more advanced talks tied to his name, including recent ones at the Simons Institute for the Theory of Computing. (YouTube)
These are great for capturing both the intuition and the flavour of his thinking.
📚 Reading List
Below are suggested readings: some are by Karp (or his core work), others are about his topics (NP-completeness, algorithms). Because I couldn’t find a publicly published full “Karp reading list” curated by him, I’m giving a recommended list rather than a definitive list.
Core / Must-Read
・ Reducibility Among Combinatorial Problems (1972) by Karp — his foundational paper that lists the 21 NP-complete problems. (cgi.di.uoa.gr)
・ “The 21 NP-complete problems” (various expositions) — e.g., the Wikipedia article “Karp’s 21 NP-complete problems” gives good overview. (Wikipedia)
・ “Computational Complexity: A Modern Approach” by Sanjeev Arora & Boaz Barak — good modern context for NP-completeness (although not by Karp) and it mentions his work. (BookAuthority)
Broader Context / Further Depth
・ Any algorithm/design book that covers NP‐completeness, reductions, etc., to see how Karp’s ideas fit into the bigger landscape.
・ Research/biography piece: “Richard Karp” on the Simons Foundation site — gives good background on his contributions beyond just NP-completeness. (Simons Foundation)
How to Use These Lists
・ Start with the 1972 paper to get the original.
・ Then watch one of the videos (the lecture) so you hear how Karp approaches the problem.
・ Follow with a broader book or article to see how the field built out from his work.
・ Along the way, make a list of “his problems” (the 21) and pick one or two to work through in more detail (e.g., graph-colouring, TSP, knapsack) to internalize the reduction concept.
・ Bonus: Seek out his later work (matching algorithms, flows, computational biology) to see how his thinking evolved.