Karps 21 NP-vollständige Probleme

Eines der bedeutendsten Resultate der Komplexitätstheorie ist der von Stephen Cook im Jahr 1971 erbrachte Nachweis, dass das Erfüllbarkeitsproblem der Aussagenlogik (meist nur kurz SAT genannt) NP-vollständig ist.

1972 griff Richard Karp diese Idee auf und zeigte für 21 verschiedene kombinatorische und graphentheoretische Probleme, die dafür bekannt waren, dass sie sich hartnäckig einer effizienten algorithmischen Lösbarkeit entzogen, dass diese ebenfalls NP-vollständig sind.

Indem er aufzeigte, dass eine große Anzahl von bedeutenden Problemen NP-vollständig sind, motivierte Karp die weitere Erforschung der Klasse NP, der Theorie der NP-Vollständigkeit sowie der Fragestellung, ob die Klassen P und NP identisch sind oder sich unterscheiden (P-NP-Problem). Letzteres zählt heute zu den wichtigsten offenen mathematischen Fragestellungen. Unter anderem zählt es zu den sieben Millennium-Problemen des Clay Mathematics Institute, für deren Lösung Preisgelder von jeweils einer Million US-Dollar ausgelobt wurden.

Liste der Probleme

Der folgende Baum zeigt Karps 21 Probleme, inklusive der zugehörigen Reduktion, die er nutzte, um ihre NP-Vollständigkeit nachzuweisen. Zum Beispiel wurde die NP-Vollständigkeit des Rucksackproblems gezeigt, indem das Problem der exakten Überdeckung darauf reduziert wurde.

• SATISFIABILITY: das Erfüllbarkeitsproblem der Aussagenlogik für Formeln in Konjunktiver Normalform
  • CLIQUE: Cliquenproblem
    • SET PACKING: Mengenpackungsproblem
    • VERTEX COVER: Knotenüberdeckungsproblem
      • SET COVERING: Mengenüberdeckungsproblem
      • FEEDBACK ARC SET: Feedback Arc Set
      • FEEDBACK NODE SET: Feedback Vertex Set
      • DIRECTED HAMILTONIAN CIRCUIT: siehe Hamiltonkreisproblem
        • UNDIRECTED HAMILTONIAN CIRCUIT: siehe Hamiltonkreisproblem
  • 0-1 INTEGER PROGRAMMING: siehe Integer Linear Programming
  • 3-SAT: siehe 3-SAT
    • CHROMATIC NUMBER: graph coloring problem
      • CLIQUE COVER: Covering by cliques
      • EXACT COVER: Problem der exakten Überdeckung
        • 3-dimensional MATCHING: 3-dimensional matching (Stable Marriage mit drei Geschlechtern)
        • STEINER TREE: Steinerbaumproblem
        • HITTING SET: Hitting-Set-Problem
        • KNAPSACK: Rucksackproblem
          • JOB SEQUENCING: Job sequencing
          • PARTITION: Partitionsproblem
            • MAX-CUT: Maximaler Schnitt

Literatur

• Richard M. Karp: Reducibility Among Combinatorial Problems. In: R. E. Miller, J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York 1972, S. 85–103.