NP-Vollständigkeit und der Satz von Cook–Levin
Lesen anpassen
Nach dieser Lektion kannst du
NP-Schwere und NP-Vollständigkeit mit der richtigen Reduktionsrichtung definieren,
begründen, warum ein Polynomialzeit-Algorithmus für ein NP-vollständiges Problem P=NP ergäbe,
die Cook–Levin-Konstruktion über einen Verifizierer, einen Schaltkreis und lokale Klauseln erklären,
Worst-Case-Schwere von Unentscheidbarkeit und der Schwierigkeit einzelner Instanzen unterscheiden.
Vorausgesetzt: Die Klassen P und NP, Reduktionen und der Satz von Rice
Bei einer Tourenplanung, einer Schaltungsbelegung und der Auswahl kompatibler Objekte scheinen jeweils andere Schwierigkeiten aufzutreten. Ein vorgeschlagener Plan lässt sich oft schnell prüfen, aber eine gute allgemeine Suchmethode fehlt. Man könnte nun für jedes Problem getrennt nach einem schnellen Algorithmus suchen.
Die Komplexitätstheorie fragt zusätzlich, ob sich diese Suchaufgaben ineinander übersetzen lassen. Wenn jedes Problem aus NP effizient in ein einziges Problem B übersetzbar wäre, dann würde ein schneller B-Algorithmus auf einen Schlag alle Probleme aus NP lösen. NP-Vollständigkeit beschreibt genau diese besondere Stellung. Wir leiten die Begriffe her und untersuchen, warum bereits das Erfüllen einer booleschen Formel diese Stellung besitzt.
Polynomielle many-one-Reduktion
Für Entscheidungsprobleme A und B bedeutet : Es gibt eine totale Funktion f, die in Polynomialzeit berechnet wird und für jede Eingabe x die Antwort erhält. Gemessen wird die Laufzeit in der Länge der Kodierung x. Die Zielinstanz darf größer werden, aber nur polynomiell: Schon ihre Ausgabe benötigt Rechenzeit.
Die Reduktion löst A nicht selbst. Sie erzeugt genau eine B-Instanz. Eine Ja-Instanz von A muss zu einer Ja-Instanz von B werden und eine Nein-Instanz zu einer Nein-Instanz. Bei ungültigen Kodierungen muss das Verfahren ebenfalls eine passende feste Nein-Instanz liefern, wenn ungültige Eingaben als Nein gelten.
Schnelle Lösungen übertragen sich rückwärts zur Reduktionsrichtung
Aus und folgt . Polynomielle Reduktionen sind außerdem transitiv.
Berechne f(x) und starte darauf den B-Entscheider. Benötigt f höchstens p(n) Schritte und damit höchstens p(n) Ausgabezeichen, und benötigt der Entscheider auf Länge m höchstens q(m) Schritte, dann ist die Gesamtzeit durch beschränkt. Das ist wieder ein Polynom. Ebenso ist die Verkettung zweier Reduktionsfunktionen polynomiell und erhält beide Antworten. Die Pfeilrichtung A→B bezeichnet also die Übersetzung; eine schnelle Lösung für B hilft danach auch für A.
NP-schwer und NP-vollständig
Ein Entscheidungsproblem B ist NP-schwer, wenn sich jedes Problem A aus NP polynomiell auf B reduzieren lässt. B ist NP-vollständig, wenn es zusätzlich selbst in NP liegt. Für diesen zweiten Teil benötigt man polynomiell lange Zertifikate und einen Polynomialzeit-Verifizierer.
Die beiden Pflichten sind unabhängig: Ein Verifizierer beweist noch keine Schwere, und ein Schwerebeweis liefert noch keinen Verifizierer. Im Deutschen bedeutet „schwer“ hier eine präzise Reduktionseigenschaft und keine Aussage über jede einzelne Eingabe.
A ist bereits NP-vollständig. Du willst zeigen, dass B NP-schwer ist. Welche Richtung wird gebraucht?
Warum ein einziges NP-vollständiges Problem genügt
Liegt ein NP-vollständiges Problem B in P, dann gilt P=NP. Umgekehrt läge bei P=NP jedes NP-vollständige Problem in P.
Für jedes gibt es eine polynomielle Reduktion auf B. Ein Polynomialzeit-Entscheider für B würde deshalb nach dem vorigen Satz auch A in Polynomialzeit entscheiden. Also wäre . Die andere Inklusion gilt ohnehin. Umgekehrt gehört B per Definition zu NP und damit bei Gleichheit auch zu P.
SAT, Literal, Klausel und 3-SAT
Eine boolesche Variable hat einen Wert in {0,1}, also falsch oder wahr. ¬ negiert, ∨ bedeutet „oder“ und ∧ bedeutet „und“. Eine Belegung weist allen Variablen Werte zu. SAT fragt, ob eine gegebene boolesche Formel mindestens eine Belegung besitzt, unter der sie wahr wird. Eine solche Belegung ist ein polynomiell langes Zertifikat; die Formel kann dann in Polynomialzeit ausgewertet werden.
Ein Literal ist eine Variable oder ihre Negation. Eine Klausel ist eine Oder-Verknüpfung von Literalen. Eine Formel in konjunktiver Normalform, kurz KNF, ist eine Und-Verknüpfung von Klauseln. Wir verwenden für 3-SAT die Konvention „höchstens drei Literale pro Klausel“. Leere Klauseln sind falsch; eine leere Und-Verknüpfung ist wahr. Bei der anderen üblichen Konvention „genau drei“ können kurze nichtleere Klauseln durch Wiederholen von Literalen aufgefüllt werden. Beide Fassungen sind NP-vollständig.
Satz von Cook–Levin
SAT ist NP-vollständig. Sogar 3-SAT mit höchstens drei Literalen pro Klausel ist NP-vollständig.
Die Zugehörigkeit zu NP folgt aus dem Belegungszertifikat. Für die Schwere betrachten wir einen beliebigen Polynomialzeit-Verifizierer V für eine Sprache A aus NP. Zu jeder festen Eingabe x konstruieren wir eine Formel, deren freie Belegung genau die Suche nach einem akzeptierten Zertifikat abbildet. Die folgenden Abschnitte erklären eine Konstruktion über boolesche Schaltkreise: Der Schaltkreis simuliert V, und lokale Klauseln erzwingen jede Gatterberechnung. Beide Übersetzungen haben polynomielle Größe. Ihre Korrektheit in beiden Richtungen ergibt genau dann, wenn die erzeugte 3-KNF erfüllbar ist. Damit gilt für jedes A aus NP die benötigte polynomielle Reduktion.
Vom Verifizierer zum endlichen Schaltkreis
Vom Verifizierer zum endlichen Schaltkreis
Die Eingabe x ist fest, das gesuchte Zertifikat y noch frei. Seine Länge ist polynomiell beschränkt. Kürzere Zertifikate können durch eine mitcodierte Länge und Auffüllung dargestellt werden. Eine polynomielle Schranke T umfasst Eingabelänge, Zertifikatslänge und Laufzeit des festen Verifizierers. Nach vorzeitigem Halt bleibt der Endzustand bis Schritt T unverändert.
Codiere eine Maschinenkonfiguration mit endlich vielen Bits je Bandzelle: Symbol, gegebenenfalls Kopfposition und Maschinenzustand. In T Schritten werden nur O(T) Zellen benötigt.
Ein UND-Gatter durch drei kurze Klauseln beschreiben
Ein UND-Gatter durch drei kurze Klauseln beschreiben
Ein Schaltkreis kann aus UND- und NICHT-Gattern sowie Konstanten aufgebaut werden. Jede Gatterausgabe erhält eine neue Variable. Für ein UND-Gatter mit Eingängen a,b und Ausgabe z soll gelten. Die ersten beiden Klauseln verbieten z=1, wenn ein Eingang null ist; die dritte verlangt z=1, wenn beide Eingänge eins sind.
Bei a=1,b=0 erzwingt die zweite Klausel z=0. Bei a=b=1 erzwingt die dritte Klausel z=1. Die Klauseln erlauben daher genau die vier korrekten Tripel (a,b,z), nicht alle acht möglichen Tripel. Für ein NICHT-Gatter genügen . Eine Konstante und die Forderung „Gesamtausgang eins“ lassen sich jeweils als Klausel mit einem Literal schreiben.
Die Zusatzvariable muss die Gatterausgabe beschreiben
| a | b | z = a ∧ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Die drei Klauseln erzwingen dieselben vier Zeilen wie das Gatter. Eine neue Variable darf nicht unabhängig gewählt werden, wenn sie eine berechnete Ausgabe vertreten soll.
Warum die gesamte Formel genau die richtige Frage stellt
Warum die gesamte Formel genau die richtige Frage stellt
Verknüpfe die Gatterbedingungen, die festgelegten Eingangsbits und die Forderung nach akzeptierendem Ausgang durch ∧. Jedes Gatter trägt nur konstant viele Klauseln bei. Die Formel wächst daher polynomiell mit dem Schaltkreis.
Gibt es ein akzeptiertes Zertifikat y, belege die Zertifikatseingänge damit und jede weitere Variable mit dem tatsächlich berechneten Gatterwert. Alle lokalen Klauseln und der akzeptierende Ausgang sind erfüllt.
NP-schwer bedeutet nicht automatisch in NP
NP-schwer bedeutet nicht automatisch in NP
Das Halteproblem H ist ebenfalls NP-schwer. Aus einer SAT-Formel φ kann man in Polynomialzeit den Code eines Programms schreiben, das alle Belegungen aufzählt und genau beim Finden einer erfüllenden Belegung hält. Falls alle Belegungen erfolglos geprüft wurden, läuft es absichtlich endlos weiter. Zusammen mit einer festen leeren Eingabe ergibt dieser Code eine Halteprobleminstanz, die genau bei erfüllbarem φ eine Ja-Antwort hat.
Damit gilt , und wegen Cook–Levin ist H NP-schwer. H liegt aber nicht in NP, denn jede NP-Sprache ist entscheidbar, H dagegen nicht. Also ist H nicht NP-vollständig. Die möglicherweise lange Ausführung des erzeugten Programms ändert nichts an der kurzen Laufzeit seiner Codeerzeugung.
NP-vollständig heißt bewiesen exponentiell oder auf jeder Eingabe schwer
NP-vollständig heißt bewiesen exponentiell oder auf jeder Eingabe schwer
Aus einem NP-Vollständigkeitsbeweis wird manchmal sofort „Dafür gibt es keinen schnellen Algorithmus“ oder sogar „Jede Instanz braucht exponentielle Zeit“ gemacht.
Ob P=NP gilt, ist offen. Ein NP-Vollständigkeitsbeweis zeigt die Konsequenz eines allgemeinen Polynomialzeit-Algorithmus, keine bewiesene exponentielle untere Schranke. Viele einzelne Instanzen können einfach sein. NP-vollständige Probleme sind außerdem entscheidbar: Eine endliche Suche über alle beschränkt langen Zertifikate genügt grundsätzlich. Unentscheidbarkeit ist eine andere Grenze.
Zusammenfassung
übersetzt beide Antworten in Polynomialzeit. Eine schnelle B-Lösung hilft dadurch bei A.
NP-schwer verlangt Reduktionen von allen NP-Problemen; NP-vollständig verlangt zusätzlich Zugehörigkeit zu NP.
Ein NP-vollständiges Problem in P würde P=NP ergeben.
Cook–Levin übersetzt einen beliebigen NP-Verifizierer in einen polynomiell großen Schaltkreis und dann in eine erfüllbarkeitserhaltende 3-KNF.
Lokale Gatterklauseln und eine akzeptierende Ausgangsklausel sind beide nötig.
Die Reduktionsfunktion erzeugt eine Instanz; sie muss deren Lösung nicht finden.
NP-Vollständigkeit ist eine Worst-Case-Aussage und kein Unentscheidbarkeitsbeweis.
Übungen
Was muss für NP-Vollständigkeit von B gezeigt werden?
3-SAT ist NP-vollständig. Du findest einen Verifizierer für B und eine Reduktion . Was folgt allein daraus?
Wie viele der acht Belegungen für a,b,z erfüllen die drei angegebenen UND-Gatterklauseln gemeinsam?
Ein Schaltkreis besteht aus zehn UND-Gattern und freien Eingangsvariablen. Jedes Gatter wird durch drei Klauseln codiert; zusätzlich wird der letzte Ausgang auf eins festgelegt. Wie viele Klauseln entstehen ohne Vereinfachung?
Warum genügt es bei Cook–Levin nicht, nur alle Gatterbedingungen hinzuschreiben und die Forderung nach Ausgang eins wegzulassen?
Was würde ein allgemeiner Polynomialzeit-Algorithmus für 3-SAT beweisen?
Erkläre am Halteproblem, weshalb NP-schwer allein keine NP-Vollständigkeit bedeutet.
Eine Reduktion produziert zu einer n Zeichen langen Eingabe einen Graphen mit ausdrücklich aufgeführten Knoten. Kann dies eine Polynomialzeit-Reduktion in einer üblichen expliziten Graphkodierung sein?