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
Literatur
Einzelnachweise
Kategorie:Komplexitätstheorie