Karps 21 NP-vollständige Probleme

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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]

1972 griff Richard Karp diese Idee auf und zeigte für 21 verschiedene kombinatorische und graphentheoretische Probleme, die dafür bekannt waren, dass sie sich hartnäckig einer effizienten algorithmischen Lösbarkeit entzogen, dass diese ebenfalls NP-vollständig sind.

Indem er aufzeigte, dass eine große Anzahl von bedeutenden Problemen 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[Bearbeiten]

Der folgende Baum zeigt Karps 21 Probleme, inklusive der zugehörigen Reduktion, die er nutzte, um ihre NP-Vollständigkeit nachzuweisen. Zum Beispiel wurde die NP-Vollständigkeit des Rucksackproblems gezeigt, indem das Problem der exakten Überdeckung darauf reduziert wurde.

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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 (http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047).