NP-Vollständigkeit und Reduktionen

Ein NP-vollständiges Problem gehört zu den schwierigsten in der Klasse NP, in dem Sinne, dass jedes NP-Problem effizient auf es reduziert werden kann. Eine schnelle Lösung eines einzelnen NP-vollständigen Problems würde somit alle anderen lösen.

Definition

Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes Problem in NP durch eine polynomielle Reduktion auf es reduziert werden kann; solche Probleme sind die maximal schwierigen Mitglieder von NP, die bis auf effiziente Transformationen äquivalent zueinander sind.

Scope

Dieses Thema behandelt die Problemklasse NP, die in polynomieller Zeit verifizierbar ist, polynomielle Many-One-Reduktionen, den Satz von Cook-Levin, der die Erfüllbarkeit als NP-vollständig etabliert, Karps Katalog NP-vollständiger kombinatorischer Probleme und die Methodik, neue Probleme durch Reduktion von bekannten als NP-vollständig zu beweisen.

Core questions

• Was bedeutet es, wenn ein Problem zu den schwierigsten in NP gehört?
• Wie identifiziert der Satz von Cook-Levin ein erstes NP-vollständiges Problem?
• Wie werden Reduktionen verwendet, um zu beweisen, dass ein neues Problem NP-vollständig ist?
• Warum hat die NP-Vollständigkeit eines Problems Auswirkungen auf Tausende anderer?

Key theories

Satz von Cook-Levin

Die Boolesche Erfüllbarkeit ist NP-vollständig, da die Berechnung jedes polynomiellen Verifizierers als Instanz der Erfüllbarkeit kodiert werden kann, was das grundlegende vollständige Problem liefert, aus dem andere abgeleitet werden.

Karp-Reduktionen und das Netz der NP-vollständigen Probleme

Karp zeigte, dass einundzwanzig natürliche Probleme, von der Graphenfärbung bis zum Entscheidungsproblem des Handelsreisenden, durch polynomielle Reduktionen NP-vollständig sind, was die Praxis der Härtebestimmung durch ein wachsendes Netzwerk von Reduktionen begründete.

Clinical relevance

NP-Vollständigkeit ist die praktische Diagnose der Unlösbarkeit: Sobald ein Problem in der Zeitplanung, Logistik, im Design oder in der Verifikation als NP-vollständig erwiesen ist, suchen Ingenieure nicht länger nach einem garantiert schnellen exakten Algorithmus, sondern greifen auf Approximationsalgorithmen, Heuristiken, Integer-Programming-Solver oder Einschränkungen zurück, die das Problem handhabbar machen.

History

Cook bewies 1971 die NP-Vollständigkeit der Erfüllbarkeit, und Levin erzielte unabhängig davon in der Sowjetunion äquivalente Ergebnisse. 1972 demonstrierte Karp einundzwanzig weitere NP-vollständige Probleme, wodurch die Allgegenwart des Phänomens aufgedeckt und die NP-Vollständigkeit zum zentralen Werkzeug zur Diagnose der rechnerischen Schwierigkeit wurde.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

Wofür steht NP?

NP steht für nichtdeterministische polynomielle Zeit. Äquivalent dazu ist ein Problem in NP, wenn eine vorgeschlagene Lösung in polynomieller Zeit überprüft werden kann, auch wenn das Finden einer solchen Lösung schwierig erscheint. Die Route des Handelsreisenden unterhalb einer gegebenen Länge ist leicht zu überprüfen, sobald sie gegeben ist, aber anscheinend schwer zu entdecken.

Wie beweist man, dass ein neues Problem NP-vollständig ist?

Man zeigt zwei Dinge: dass das Problem in NP liegt, sodass Kandidatenlösungen schnell überprüfbar sind, und dass ein bekanntes NP-vollständiges Problem in polynomieller Zeit auf es reduziert werden kann. Die Reduktion überträgt die bekannte Härte und platziert das neue Problem unter den schwierigsten in NP.