# Richard Karp

> 1935– · Computer Scientist
>
> **Recorded contribution:** Karp's 21 NP-complete problems; Rabin-Karp algorithm; computational biology

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

Richard Karp (born 1935) turned Stephen Cook's abstract NP-completeness result into a map of concrete computational difficulty. His 1972 paper gave polynomial-time reductions from Boolean satisfiability to twenty-one combinatorial problems, including clique, vertex cover, Hamiltonian cycle, and scheduling variants. This did not prove that the problems require exponential time or that P differs from NP. It showed that an efficient algorithm for any NP-complete member would efficiently solve every problem in NP. Karp also contributed matching, network-flow, string-search, randomized, and computational-biology algorithms, making him a bridge between complexity classification and practical algorithm design.

## 2. The problem inherited

Researchers knew SAT was NP-complete but lacked a broad demonstration that familiar graph, set, and scheduling problems shared the same deep computational barrier.

## 3. The central contribution

Karp developed a reusable reduction method and proved twenty-one diverse problems NP-complete, establishing completeness as a practical taxonomy rather than one isolated theorem.

## 4. Reconstruct the mechanism

1. Start from a problem already known NP-complete and select a target decision problem whose instances can encode its choices.
2. Construct the target instance in polynomial time, using gadgets that preserve constraints and feasible assignments.
3. Prove both directions: every source solution yields a target solution and every target solution decodes to a source solution.
4. Combine the reduction with a polynomial verifier for the target, establishing NP-hardness and membership in NP.

## 5. What changed downstream

- NP-completeness became a standard way to recognize when exact polynomial algorithms are unlikely.
- The catalog motivated approximation, parameterized, heuristic, and exponential algorithms with explicit tradeoffs.
- Reductions became a common language connecting apparently unrelated optimization domains.

## 6. Attribution, limits, and uncertainty

- Cook and independently Levin established the foundational theorem; Karp extended it to a broad catalog.
- NP-complete does not mean impossible, undecidable, or slow on every practical instance.
- A reduction can be theoretically polynomial while distorting instance structure so much that it gives weak empirical guidance.

## 7. Reconstruction lab

Reduce a small 3-SAT formula to clique using one vertex per literal occurrence and edges between compatible choices from different clauses. Prove both directions and measure how the graph size grows with clauses.

## 8. Evidence trail

- [Reducibility Among Combinatorial Problems](https://doi.org/10.1007/978-1-4684-2001-2_9) — Springer
- [Richard Karp](https://www2.eecs.berkeley.edu/Faculty/Homepages/karp.html) — University of California, Berkeley

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*