#tag-refactored algorithms complexity computerscience computing cs csci3434 karp np np-complete np-hard npcomplete problem theory winter2008

My tags:

From Wikipedia, the free encyclopedia

One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first (practically relevant) NP-complete problem, the boolean satisfiability problem.^[1] 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 its computational intractability, are NP-complete.^[2]

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.

[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 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)
    • SET PACKING
    • VERTEX COVER
      • SET COVERING
      • FEEDBACK NODE SET
      • FEEDBACK ARC SET
      • DIRECTED HAMILTON CIRCUIT (Karp's name, now usually called DIRECTED HAMILTONIAN CIRCUIT)
        • UNDIRECTED HAMILTON CIRCUIT (Karp's name, now usually called UNDIRECTED HAMILTONIAN CIRCUIT)
  • SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE (equivalent to 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 to Subset sum)
          • 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 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.^[3]

[edit] See also

• List of NP-complete problems

[edit] References

1. ^ Stephen Cook (1971). "The Complexity of Theorem Proving Procedures". Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158. 
2. ^ 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. 
3. ^ David Zuckerman (1996). "On Unapproximable Versions of NP-Complete Problems". SIAM Journal on Computing 25 (6): 1293–1304. doi:10.1137/S0097539794266407. http://citeseer.ist.psu.edu/192662.html.