Karp's 21 NP-complete problems

From Wikipedia, the free encyclopedia

One of the most important results of computational complexity theory was Stephen Cook's 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. In 1972, Richard 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 their intractability, were all NP-complete.

By 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 fact that no one had found an efficient algorithm for any of them, despite never knowing they were NP-complete, was the first strong evidence that P ≠ NP.

[edit] 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 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 also independent set problem)
    • SET PACKING
    • VERTEX COVER
      • SET COVERING
      • FEEDBACK ARC SET
      • FEEDBACK NODE SET
      • DIRECTED HAMILTONIAN CIRCUIT
        • UNDIRECTED HAMILTONIAN CIRCUIT
  • 3-SAT
    • CHROMATIC NUMBER
      • CLIQUE COVER
      • EXACT COVER
        • 3-dimensional MATCHING
        • STEINER TREE
        • HITTING SET
        • KNAPSACK
          • JOB SEQUENCING
          • PARTITION
            • MAX-CUT

As 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 would show in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within some constant factor unless P = NP.

[edit] See also

• List of NP-complete problems

[edit] References

• Richard M. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum, p.85-103. 1972.
• S. Smale. P versus NP. Lecture slides (in German), pg.41.
• David Zuckerman. On Unapproximable Versions of NP-Complete Problems. SIAM Journal on Computing, volume 25, number 6, p.1293-1304. 1996.