NP-Vollständigkeit und Unlösbarkeit

NP-Vollständigkeit identifiziert die schwierigsten Probleme in der Klasse NP – jene, auf die sich jedes NP-Problem reduzieren lässt – und bietet den Standardrahmen zur Erkennung von Problemen, für die kein effizienter Algorithmus bekannt oder wahrscheinlich ist.

Definition

Ein Entscheidungsproblem ist NP-vollständig, wenn es in NP liegt (seine Ja-Instanzen verfügen über effizient verifizierbare Zertifikate) und jedes Problem in NP in Polynomzeit auf es reduziert werden kann; solche Probleme sind die schwierigsten in NP, und ein Polynomzeit-Algorithmus für eines würde einen für alle liefern.

Scope

Dieses Thema behandelt die Komplexitätsklassen P und NP, Polynomzeit-Reduktionen, die Definitionen von NP-Schwere und NP-Vollständigkeit, das Cook-Levin-Theorem, das die Erfüllbarkeit als NP-vollständig etabliert, Karps Katalog NP-vollständiger Probleme und die praktischen Konsequenzen der Unlösbarkeit für den Algorithmenentwurf. Es wendet diese Konzepte auf die Erkennung und den Umgang mit schwierigen Problemen an; die breitere formale Theorie der Komplexitätsklassen wird im Teilgebiet der theoretischen Informatik behandelt.

Core questions

• Was unterscheidet die Komplexitätsklassen P und NP?
• Wie überträgt eine Polynomzeit-Reduktion die Schwierigkeit von einem Problem auf ein anderes?
• Was besagt das Cook-Levin-Theorem, und warum ist die Erfüllbarkeit zentral?
• Wie wird ein neues Problem durch Reduktion von einem bekannten als NP-vollständig bewiesen?
• Welche algorithmischen Strategien bleiben, wenn ein Problem als NP-schwer erwiesen ist?

Key concepts

• Komplexitätsklasse P
• Komplexitätsklasse NP
• Polynomzeit-Reduktion
• NP-Schwere
• NP-Vollständigkeit
• Cook-Levin-Theorem
• Boolesche Erfüllbarkeit (SAT)
• P-versus-NP-Problem

Key theories

Cook-Levin-Theorem

Das Cook-Levin-Theorem beweist, dass die Boolesche Erfüllbarkeit (SAT) NP-vollständig ist: Jedes Problem in NP lässt sich in Polynomzeit auf sie reduzieren, was das erste NP-vollständige Problem und den Anker für den Beweis der Schwierigkeit anderer Probleme liefert.

Reduzierbarkeit zwischen kombinatorischen Problemen

Karp zeigte, dass Polynomzeit-Reduktionen viele natürliche Probleme – Clique, Vertex Cover, Hamiltonkreis, Partition und andere – zu einem Netz NP-vollständiger Probleme verbinden, sodass jedes durch Reduktion von einem anderen als schwierig bewiesen werden kann.

Clinical relevance

Die Erkenntnis, dass ein Problem NP-vollständig ist, gehört zu den praktisch nützlichsten Ergebnissen in der Informatik: Sie weist Ingenieure darauf hin, keinen schnellen exakten Algorithmus zu erwarten und stattdessen Approximationsalgorithmen, Heuristiken, für typische Instanzen optimierte exakte Löser oder Einschränkungen auf lösbare Spezialfälle einzusetzen. Viele Planungs-, Routing-, Pack- und Entwurfsprobleme sind NP-vollständig.

History

Stephen Cook führte die NP-Vollständigkeit 1971 ein und bewies, dass SAT NP-vollständig ist; Leonid Levin erzielte unabhängig ähnliche Ergebnisse. Richard Karps Arbeit von 1972 zeigte, dass 21 natürliche Probleme NP-vollständig sind, und etablierte damit die Reichweite des Rahmens. Garey und Johnsons Buch von 1979 katalogisierte Hunderte von NP-vollständigen Problemen und wurde zum Standardwerk.

Debates

P versus NP

Ob P gleich NP ist – ob jedes effizient verifizierbare Problem auch effizient lösbar ist – ist das wichtigste offene Problem in diesem Bereich; fast alle Forscher vermuten, dass P ungleich NP ist, aber die Frage ist ungelöst und ein Millennium-Preisproblem.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

Was ist der Unterschied zwischen NP-schwer und NP-vollständig?

Ein Problem ist NP-schwer, wenn sich jedes NP-Problem in Polynomzeit auf es reduzieren lässt, es muss aber nicht selbst in NP liegen und kein Entscheidungsproblem sein. Ein Problem ist NP-vollständig, wenn es sowohl NP-schwer als auch in NP ist. NP-vollständige Probleme sind die schwierigsten Probleme, die noch in NP liegen.

Bedeutet NP-Vollständigkeit, dass ein Problem niemals gelöst werden kann?

Nein. Es bedeutet, dass kein Polynomzeit-Algorithmus für alle Eingaben bekannt ist und wahrscheinlich keiner existiert, wenn P ungleich NP ist. In der Praxis werden solche Probleme mit Approximationsalgorithmen, Heuristiken, exponentiellen Lösern, die auf realistischen Instanzen funktionieren, oder durch Einschränkung auf Spezialfälle angegangen.