Lektion 4.2

NP-Vollständigkeit und der Satz von Cook–Levin

50 min Lesezeit
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.

Definition

Polynomielle many-one-Reduktion

Für Entscheidungsprobleme A und B bedeutet A≤pBA\le_p B: 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.

x∈A  ⟺  f(x)∈Bx\in A\iff f(x)\in B
Satz

Schnelle Lösungen übertragen sich rückwärts zur Reduktionsrichtung

Aus A≤pBA\le_p B und B∈PB\in\mathrm P folgt A∈PA\in\mathrm P. Polynomielle Reduktionen sind außerdem transitiv.

Definition

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.

B NP-vollsta¨ndig  ⟺  B∈NPund∀A∈NP:A≤pBB\text{ NP-vollständig}\iff B\in\mathrm{NP}\quad\text{und}\quad\forall A\in\mathrm{NP}:A\le_p B
Kurz geprüft

A ist bereits NP-vollständig. Du willst zeigen, dass B NP-schwer ist. Welche Richtung wird gebraucht?

Satz

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.

Definition

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

Satz von Cook–Levin

SAT ist NP-vollständig. Sogar 3-SAT mit höchstens drei Literalen pro Klausel ist NP-vollständig.

Schritt für Schritt

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.

  1. Codiere eine Maschinenkonfiguration mit endlich vielen Bits je Bandzelle: Symbol, gegebenenfalls Kopfposition und Maschinenzustand. In T Schritten werden nur O(T) Zellen benötigt.

Schritt 1 von 4
Beispiel

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 z↔(a∧b)z\leftrightarrow(a\land b) gelten. Die ersten beiden Klauseln verbieten z=1, wenn ein Eingang null ist; die dritte verlangt z=1, wenn beide Eingänge eins sind.

(¬z∨a)∧(¬z∨b)∧(z∨¬a∨¬b)(\neg z\lor a)\land(\neg z\lor b)\land(z\lor\neg a\lor\neg b)

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 z=¬az=\neg a genügen (z∨a)∧(¬z∨¬a)(z\lor a)\land(\neg z\lor\neg a). Eine Konstante und die Forderung „Gesamtausgang eins“ lassen sich jeweils als Klausel mit einem Literal schreiben.

Die Zusatzvariable muss die Gatterausgabe beschreiben

abUNDz
Erlaubte Belegungen des Gatters
abz = a ∧ b
000
010
100
111

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.

Schritt für Schritt

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.

  1. 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.

Schritt 1 von 2
Beispiel

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 SAT≤pH\mathrm{SAT}\le_p H, 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.

Häufige Fehler

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.

Richtig ist

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

  • A≤pBA\le_p B ü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

Aufgabe 1Multiple Choice

Was muss für NP-Vollständigkeit von B gezeigt werden?

Aufgabe 2Multiple Choice

3-SAT ist NP-vollständig. Du findest einen Verifizierer für B und eine Reduktion B≤p3SATB\le_p\mathrm{3SAT}. Was folgt allein daraus?

Aufgabe 3Numerisch

Wie viele der acht Belegungen für a,b,z erfüllen die drei angegebenen UND-Gatterklauseln gemeinsam?

Aufgabe 4Numerisch

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?

Aufgabe 5Freitext

Warum genügt es bei Cook–Levin nicht, nur alle Gatterbedingungen hinzuschreiben und die Forderung nach Ausgang eins wegzulassen?

Aufgabe 6Multiple Choice

Was würde ein allgemeiner Polynomialzeit-Algorithmus für 3-SAT beweisen?

Aufgabe 7Freitext

Erkläre am Halteproblem, weshalb NP-schwer allein keine NP-Vollständigkeit bedeutet.

Aufgabe 8Freitext

Eine Reduktion produziert zu einer n Zeichen langen Eingabe einen Graphen mit 2n2^n ausdrücklich aufgeführten Knoten. Kann dies eine Polynomialzeit-Reduktion in einer üblichen expliziten Graphkodierung sein?