Quelltext der Seite Karps 21 NP-vollständige Probleme

'''Karps 21 NP-vollständige Probleme''' ist eine in der [[Komplexitätstheorie]] gebräuchliche Menge [[NP-Vollständigkeit|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.<ref name="Cook-1971" />

Im Jahr 1972 griff [[Richard M. Karp|Richard Karp]] diese Idee auf und zeigte die NP-Vollständigkeit ebenfalls für 21 weitere [[Kombinatorik|kombinatorische]] und [[Graphentheorie|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-Probleme]]n 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 [[Rucksackproblem]]s durch Reduzierung des [[Problem der exakten Überdeckung|Problems der exakten Überdeckung]] darauf gezeigt.

* SATISFIABILITY: das [[Erfüllbarkeitsproblem der Aussagenlogik]] für Formeln in [[Konjunktive Normalform|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 [[Ganzzahlige lineare Optimierung|Integer Linear Programming]]
** 3-SAT: siehe [[3-SAT]]
*** CHROMATIC NUMBER: [[Färbung (Graphentheorie)|graph coloring problem]]
**** CLIQUE COVER: [[Covering by cliques]]
**** EXACT COVER: [[Problem der exakten Überdeckung]]
***** 3-dimensional MATCHING: [[3-dimensional matching]] ([[Globales_Matching#Stable_Marriage|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 ==

* {{Literatur
 | Autor = [[Richard M. Karp]]
 | Titel = Reducibility Among Combinatorial Problems
 | Online = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
 | Sammelwerk = Complexity of Computer Computations
 | Herausgeber = R. E. Miller und J. W. Thatcher
 | Verlag = Plenum Press, New York
 | Seiten = 85–103
 | Jahr = 1972
}}

== Einzelnachweise ==
<references>
<ref name="Cook-1971">
{{Literatur
 | Autor = [[Stephen Cook]]
 | Jahr = 1971
 | Titel = The Complexity of Theorem Proving Procedures
 | Online = http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047
 | Sammelwerk = Proceedings of the third annual ACM symposium on Theory of computing
 | Seiten = 151–158
}}
</ref>
</references>

[[Kategorie:Komplexitätstheorie]]