Karps 21 NP-vollständige Probleme
# 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.
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