Karp's 21 NP-complete Problems - The Problems

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 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).

Read more about this topic:  Karp's 21 NP-complete Problems

Famous quotes containing the word problems:

    “If family communication is good, parents can pick up the signs of stress in children and talk about it before it results in some crisis. If family communication is bad, not only will parents be insensitive to potential crises, but the poor communication will contribute to problems in the family.”
    —Donald C. Medeiros (20th century)

    “Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan “Press On”, has solved and will always solve the problems of the human race.”
    —Calvin Coolidge (1872–1933)