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
    - 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

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).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[Cook-1971-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).