Karps 21 NP-vollständige Probleme

Karps 21 NP-vollständige Probleme ist eine in der Komplexitätstheorie gebräuchliche Menge NP-vollständiger Rechenprobleme.

Geschichte

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.[1]

Im Jahr 1972 griff Richard Karp diese Idee auf und zeigte die NP-Vollständigkeit ebenfalls für 21 weitere kombinatorische und graphentheoretische Probleme, die sich hartnäckig einer effizienten algorithmischen Lösbarkeit entzogen.

Bedeutung

Indem er aufzeigte, dass eine große Anzahl bedeutender Probleme 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, einschließlich der zugehörigen Reduktion, die er zum Nachweis ihrer NP-Vollständigkeit nutzte. So wurde etwa die NP-Vollständigkeit des Rucksackproblems durch Reduzierung des Problems der exakten Überdeckung darauf gezeigt.

• 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 und J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York, 1972, S. 85–103 (uoa.gr [PDF]). 

Einzelnachweise

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