NPvollständig

NP-vollständig, kurz NP-vollständig, bezeichnet in der theoretischen Informatik jene Entscheidungsprobleme, die zwei Eigenschaften gleichzeitig erfüllen: Sie gehören zur Klasse NP und sie sind NP-hard. Ein Problem gehört zur Klasse NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann. Ein Problem ist NP-hard, wenn jedes Problem aus NP in polynomieller Zeit auf dieses Problem reduzierbar ist. Eine NP-vollständige Problemstellung ist also so hart wie die gesamte Klasse NP, vorausgesetzt man verwendet polynomielle Many-One-Reduktionen (Karp-Reduktionen).

Historisch wurden NP-vollständige Probleme durch Stephen Cook und Richard Karp etabliert; der Satz von Cook-Levin zeigte 1971, dass das Erfüllbarkeitsproblem SAT NP-vollständig ist. Seitdem wurden zahlreiche weitere Probleme als NP-vollständig bewiesen, darunter 3-SAT, CLIQUE, Vertex Cover, Hamiltonian Path/Cycle, Subset Sum und Graph Coloring für feste Farben größer oder gleich drei.

Es ist wichtig zu unterscheiden: Optimierungsversionen dieser Probleme (zum Beispiel Minimieren der Anzahl zu erfüllender Klauseln) sind oft NP-schwer, aber nicht notwendigerweise in NP. Die Frage, ob P gleich NP ist, bleibt offen; eine polynomielle Lösung für irgendein NP-vollständiges Problem würde automatisch eine polynomielle Lösung für alle NP-Probleme bedeuten (P = NP). Umgekehrt würde ein polynomielles Verfahren für ein NP-vollständiges Problem direkt bedeuten, dass P=NP.

Zusammenfassend bezeichnet NP-vollständig jene Entscheidungsprobleme, die sich in NP befinden und zugleich jedem NP-Problem polynomiell reduzierbar sind. Sie repräsentieren die härteste Klasse innerhalb von NP, deren Lösungsvoraussetzung zentrale Auswirkungen auf die Komplexitätstheorie hat.