Karp's 21 NP-complete problems
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete (also called the Cook-Levin theorem) to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable. This demonstration drove interest in the study of NP-completeness and the P = NP problem.
Karp's 21 problems, many with their original names, are shown below, with the nesting indicating the direction of the reductions used. For example, Knapsack was shown to be NP-complete by reducing Exact cover to Knapsack.
- Satisfiability: the boolean satisfiability problem for formulas in conjunctive normal form (often referred to as SAT)
- 0-1 integer programming
- Clique (see also independent set problem)
- Satisfiability with at most 3 literals per clause (equivalent to 3-SAT)
As time went on it was discovered that many of the problems can be solved efficiently if restricted to special cases, or can be solved within any fixed percentage of the optimal result. However, David Zuckerman showed in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within any constant factor unless P = NP, by showing that Karp's approach to reduction generalizes to a specific type of approximability reduction. Note however that these may be different from the standard optimization versions of the problems, which may have approximation algorithms (as in the case of maximum cut).
- Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.
- Stephen Cook (1971). "The Complexity of Theorem Proving Procedures". Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158.
- David Zuckerman (1996). "On Unapproximable Versions of NP-Complete Problems". SIAM Journal on Computing 25 (6): 1293–1304. doi:10.1137/S0097539794266407.