Karps 21 NP-complete problems

Karp's 21 NP-complete problems is a set of NP-complete arithmetic problems that is common in complexity theory .

history

One of the most important results of complexity theory is the proof provided by Stephen Cook in 1971 that the satisfiability problem of propositional logic (usually just called SAT for short ) is NP-complete.

In 1972 Richard Karp took up this idea and showed NP-completeness for 21 further combinatorial and graph-theoretical problems that stubbornly eluded efficient algorithmic solvability.

meaning

By showing that a large number of significant problems are NP-complete, Karp motivated further research into class NP, the theory of NP-completeness, and the question of whether classes P and NP are identical or different ( P-NP- Problem ). The latter is one of the most important open mathematical questions today. Among other things, it is one of the seven Millennium Problems of the Clay Mathematics Institute , for whose solution prize money of one million US dollars was awarded.

List of problems

The following tree shows Karp's 21 problems, including the associated reduction that he used to prove their NP-completeness. For example, the NP-completeness of the backpack problem was shown by reducing the problem of the exact coverage on it.

• SATISFIABILITY: the satisfiability problem of propositional logic for formulas in conjunctive normal form
  • CLIQUE: clique problem
    • SET PACKING: quantity packing problem
    • VERTEX COVER: node coverage problem
      • SET COVERING: set cover problem
      • FEEDBACK ARC SET: Feedback Arc Set
      • FEEDBACK NODE SET: Feedback Vertex Set
      • DIRECTED HAMILTONIAN CIRCUIT: see Hamilton circle problem
        • UNDIRECTED HAMILTONIAN CIRCUIT: see Hamilton circle problem
  • 0-1 INTEGER PROGRAMMING: see Integer Linear Programming
  • 3-SAT: see 3-SAT
    • CHROMATIC NUMBER: graph coloring problem
      • CLIQUE COVER
      • EXACT COVER: problem of exact coverage
        • 3-dimensional MATCHING: 3-dimensional matching ( stable marriage with three sexes)
        • STEINER TREE: Steiner tree problem
        • HITTING SET: Hitting set problem
        • KNAPSACK: Backpack problem
          • JOB SEQUENCING: Job sequencing
          • PARTITION: partition problem
            • MAX-CUT: Maximum cut

literature

• Richard M. Karp : Reducibility Among Combinatorial Problems . In: RE Miller and JW Thatcher (Eds.): Complexity of Computer Computations . Plenum Press, New York, 1972, pp. 85-103 ( uoa.gr [PDF]).

Individual evidence

1. ↑ Stephen Cook : The Complexity of Theorem Proving Procedures . In: Proceedings of the third annual ACM symposium on Theory of computing . 1971, p.  151-158 ( acm.org ).