“Reducibility Among Combinatorial Problems” was presented by Richard Karp at the Symposium on the Complexity of Computer Computations, held in 1972 at the IBM Thomas J. Watson Research Center, and published in the proceedings volume “Complexity of Computer Computations.” A full text is hosted by the University of Maryland.
The paper’s central move was to take Stephen Cook’s 1971 result, that the satisfiability problem is NP-complete, and use polynomial-time reducibility to spread that hardness across the landscape of combinatorial problems. Karp identified a list of 21 problems, including the traveling salesman problem, clique, vertex cover, graph coloring, the knapsack problem, and Hamiltonian circuit, and showed that each is NP-complete by exhibiting reductions among them.
The lasting importance of the paper is the technique as much as the list. It established the now-standard recipe for proving a new problem hard: reduce a problem already known to be NP-complete to the new one in polynomial time. Karp’s 21 problems became the canonical starting points for such reductions, which is why the paper is cited far more for its method than for any single result.
By demonstrating that so many practical, unrelated-looking problems share the same underlying difficulty, the paper made NP-completeness a working tool rather than an abstraction. It is one of the founding documents of computational complexity theory and a direct ancestor of the open P versus NP question.