NPVollständigkeit

NP-Vollständigkeit bezeichnet eine Eigenschaft von Entscheidungsproblemen in der theoretischen Informatik. Ein Problem L heißt NP-vollständig, wenn zwei Bedingungen erfüllt sind: Erstens liegt L in der Klasse NP, das heißt, eine Ja-/Nein-Entscheidung kann in polynomieller Zeit verifiziert werden, sofern man eine passende Zertifikatslösung erhält. Zweitens ist L NP-hart, was bedeutet, dass jedes Problem in NP in polynomieller Zeit auf L reduzierbar ist (polynomielle Viele-zu-eine Reduktion). Damit wären alle NP-Probleme auf L übertragbar, sodass eine polynomielle Lösung von L alle NP-Probleme lösen könnte.

Historisch wurde NP-Vollständigkeit durch den Cook-Levin-Satz eingeführt; SAT (Erfüllbarkeit boolescher Formeln) wurde als erstes NP-vollständig nachgewiesen. Seitdem wurden zahlreiche weitere Probleme als NP-vollständig klassifiziert, darunter Clique, Vertex Cover, Hamiltonian Path, Graph Coloring und Subset Sum. Die Begründung erfolgt zumeist durch Reduktionen: Man zeigt, dass jedes Problem in NP in polynomieller Zeit auf das Kandidat-Problem abgebildet werden kann.

Auswirkungen: Die NP-Vollständigkeit impliziert, dass, falls ein NP-vollständiges Problem polynomiell gelöst werden könnte, damit alle NP-Probleme in polynomieller Zeit gelöst werden könnten (P = NP). Derzeit ist ungeklärt, ob P gleich NP ist. In der Praxis bedeutet dies oft, dass für NP-vollständige Probleme nur exponentielle Algorithmen oder Heuristiken/Approximationen verwendet werden, insbesondere bei großen Eingaben.

Verwendung und Bedeutung: NP-Vollständigkeit dient als zentrale Kennzeichnung algorithmischer Schwierigkeit, hilft bei der Beurteilung der Machbarkeit von Lösungsansätzen und motiviert die Entwicklung von Strategien wie Branch-and-Bound, heuristische Suche und domänen­spezifische Algorithmen.