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:

    “Belonging to a group can provide the child with a variety of resources that an individual friendship often cannot—a sense of collective participation, experience with organizational roles, and group support in the enterprise of growing up. Groups also pose for the child some of the most acute problems of social life—of inclusion and exclusion, conformity and independence.”
    —Zick Rubin (20th century)

    “Our [adult] children have an adult’s right to make their own choices and have the responsibility of living with the consequences. If we make their problems ours, they avoid that responsibility, and we are faced with problems we can’t and shouldn’t solve.”
    —Jane Adams (20th century)