- Karp's 21 NP-complete problems
One of the most important results in

computational complexity theory wasStephen Cook 's 1971 demonstration of the first (practically relevant)NP-complete problem, theboolean satisfiability problem . [*cite book|author =*] In 1972,Stephen Cook |year = 1971|chapter = [*http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047 The Complexity of Theorem Proving Procedures*] |title = Proceedings of the third annual ACM symposium on Theory of computing|pages = 151–158Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete. [*cite book | author = Richard M. Karp | chapter = [*]*http://www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems*] | title = Complexity of Computer Computations | editor = R. E. Miller and J. W. Thatcher (editors) | publisher = New York: Plenum | pages = 85–103 | year = 1972By revealing that a large number of problems important to researchers are NP-complete, Karp motivated the study of NP, NP-completeness, and the now-famous P = NP question.

**The problems**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.

* SAT: the boolean satisfiability problem for formulas in

conjunctive normal form

** 0-1 INTEGER PROGRAMMING

** CLIQUE (see alsoindependent set problem )

*** SET PACKING

*** VERTEX COVER

**** SET COVERING

**** FEEDBACK NODE SET

**** FEEDBACK ARC SET

**** DIRECTED HAMILTONIAN CIRCUIT

***** UNDIRECTED HAMILTONIAN CIRCUIT

** 3-SAT

*** CHROMATIC NUMBER (also called the Graph Coloring Problem)

**** CLIQUE COVER

**** EXACT COVER

***** HITTING SET

***** STEINER TREE

***** 3-dimensional MATCHING

***** KNAPSACK (Karp's definition of Knapsack is closer toSubset sum )

****** JOB SEQUENCING

****** PARTITION

******* MAX-CUTAs time went on it was discovered that many of the problems can be solved 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. [

*cite journal | author = David Zuckerman | url = http://citeseer.ist.psu.edu/192662.html | title = On Unapproximable Versions of NP-Complete Problems | journal = SIAM Journal on Computing | volume = 25 | issue = 6 | pages = 1293–1304 | year = 1996 | doi = 10.1137/S0097539794266407*]**See also***

List of NP-complete problems **References**

*Wikimedia Foundation.
2010.*