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:

    “The problems of victory are more agreeable than the problems of defeat, but they are no less difficult.”
    —Winston Churchill (1874–1965)

    “If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
    —Barbara Coloroso (20th century)