Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
NP-Vollständigkeit, SAT und Reduktionen
Du weißt, dass NP-vollständige Probleme die schwersten in NP sind. Aber wie beweist man, dass ein konkretes Problem dazugehört? Die Antwort ist die polynomielle Reduktion, und der Ausgangspunkt ist fast immer SAT. Dieses Topic vertieft die Beweistechnik aus dem Komplexitätsklassen-Thema.
Was du in der Klausur können musst:
- das Beweisschema für NP-Vollständigkeit (in NP und NP-schwer)
- SAT und 3-SAT und den Satz von Cook-Levin
- die polynomielle (Karp-)Reduktion
A ≤_p Bund ihre Richtung - die Standard-Reduktion 3-SAT
≤_pCLIQUE
Die Idee in einem Satz
Ein Problem
Bist NP-vollständig, wennB ∈ NPund sich ein bereits bekanntes NP-vollständiges Problem polynomiell aufBreduzieren lässt. So vererbt sich die Schwere von Problem zu Problem, ausgehend von SAT.
SAT und 3-SAT
SAT (Erfüllbarkeitsproblem): Gegeben eine Boolesche Formel in konjunktiver Normalform (KNF), also einer Konjunktion von Klauseln, wobei jede Klausel eine Disjunktion von Literalen ist. Frage: Gibt es eine Belegung der Variablen, die alle Klauseln wahr macht?
- Beispiel:
(x₁ vee x₂ vee neg x₃) wedge (neg x₁ vee x₂ vee x₃) - 3-SAT: Spezialfall mit genau drei Literalen pro Klausel, ebenfalls NP-vollständig und der bequeme Startpunkt für Reduktionen.
Satz von Cook-Levin (1971): SAT ist NP-vollständig. Das ist das erste direkt (über die Simulation einer nichtdeterministischen Turing-Maschine) bewiesene NP-vollständige Problem. Alle weiteren folgen per Reduktion.
Polynomielle Reduktion
Eine (Karp-)Reduktion A ≤_p B ist eine in polynomieller Zeit berechenbare Abbildung, die jede Instanz von A so in eine Instanz von B übersetzt, dass gilt: A ist eine Ja-Instanz genau dann, wenn das Bild eine Ja-Instanz von B ist.
Beweisschema "B ist NP-vollständig":
B ∈ NP: ein Zertifikat (Lösungsvorschlag) ist in polynomieller Zeit prüfbar.Bist NP-schwer: reduziere ein bekanntes NP-vollständigesA(z.B. 3-SAT) aufB, alsoA ≤_p B.
Die Richtung ist entscheidend: das bekannte schwere A wird auf das neue B reduziert.
Beispiel: 3-SAT ≤_p CLIQUE
Die klassische Reduktion: Aus einer 3-SAT-Formel mit k Klauseln baut man einen Graphen. Jede Klausel wird zu einer Gruppe von Knoten (ein Knoten je Literal). Eine Kante verbindet zwei Literale aus verschiedenen Klauseln, die sich nicht widersprechen (nicht x und neg x). Gesucht wird eine Clique der Größe k.
Eine solche k-Clique wählt aus jeder Klausel ein verträgliches Literal, das ist genau eine erfüllende Belegung. Probier es aus:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Die Familie der NP-vollständigen Probleme
Von SAT ausgehend wurden über Reduktionsketten Tausende Probleme als NP-vollständig bewiesen, darunter 3-SAT, CLIQUE, Vertex-Cover, Independent-Set, Hamiltonkreis, TSP (Entscheidung), Rucksack, Subset-Sum, Graphfärbung. Sie sind durch Reduktionen miteinander verbunden: Löst man eines effizient, löst man alle effizient.
Konsequenz: Findet jemand einen Polynomialalgorithmus für irgendein NP-vollständiges Problem, dann gilt
P = NP. Bis dahin nutzt man für sie Heuristiken, Approximationen und Spezialfälle.
Klausur-Faustregeln
1. NP-vollständig = in NP UND NP-schwer. Beweis: (1) B ∈ NP, (2) bekanntes NP-vollständiges A auf B reduzieren.
2. SAT ist das erste NP-vollständige Problem (Cook-Levin 1971); 3-SAT ebenso und meist der Startpunkt.
3. Polynomielle Reduktion A ≤_p B: poly-berechenbare Abbildung mit Ja ⇔ Ja.
4. Richtung: bekanntes-schweres A auf neues B (A ≤_p B).
5. 3-SAT ≤_p CLIQUE: Klausel → Knotengruppe, Kanten zwischen verträglichen Literalen, k-Clique ⇔ erfüllbar.
6. Ein NP-vollständiges Problem in P ⇒ P = NP.
Häufige Stolpersteine
1. Nur eine Hälfte beweisen. NP-Vollständigkeit braucht beides: Zugehörigkeit zu NP und NP-Schwere.
2. Reduktionsrichtung verdrehen. Man reduziert das bekannte schwere Problem auf das neue (A ≤_p B), nicht umgekehrt.
3. Die Polynomialität der Reduktion vergessen. Nur eine in polynomieller Zeit berechenbare Reduktion überträgt die Schwere.
4. SAT und 3-SAT als grundverschieden sehen. Beide sind NP-vollständig; 3-SAT ist nur die handliche Normalform für Reduktionen.
5. "NP-vollständig" mit "unlösbar" verwechseln. Die Probleme sind lösbar (und verifizierbar), nur vermutlich nicht in Polynomialzeit.
6. Korrektheit der Reduktion unvollständig zeigen. Man muss beide Richtungen begründen: erfüllbar ⇒ k-Clique und k-Clique ⇒ erfüllbar.
Interaktiv verstehen
Die Reduktion erleben
Im Graphen wird jede Klausel zu einer Knotengruppe. Eine k-Clique (ein Knoten je Klausel, paarweise verbunden) entspricht einer erfüllenden Belegung. Lass dir die Lösung anzeigen und lies die Belegung ab.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei einer Reduktion immer drei Dinge angeben: (1) die Konstruktion (wie wird die Instanz übersetzt), (2) die Polynomialität (geht in poly Zeit), (3) die Korrektheit in beiden Richtungen (Ja ⇔ Ja).
Praxis-Übung
Klausurfragen mit Lösungen (6)
- F1.Was muss man zeigen, damit ein Problem NP-vollständig ist?
Antwort: dass es in NP liegt UND NP-schwer ist (Reduktion eines bekannten NP-vollständigen Problems)
Erklärung: NP-Vollständigkeit verlangt beide Teile: Zugehörigkeit zu NP (Zertifikat poly prüfbar) und NP-Schwere (ein bekanntes NP-vollständiges Problem ist polynomiell darauf reduzierbar).
- F2.Was fragt das Erfüllbarkeitsproblem SAT?
Antwort: ob es eine Belegung gibt, die eine Boolesche Formel wahr macht
Erklärung: SAT fragt, ob eine Boolesche Formel (in KNF) erfüllbar ist, also ob es eine Belegung der Variablen gibt, die alle Klauseln gleichzeitig wahr macht.
- F3.Um ein neues Problem B als NP-schwer zu zeigen, reduziert man ...
Antwort: ein bekanntes NP-vollständiges Problem A auf B (A ≤ₚ B)
Erklärung: Man reduziert das bekannte schwere A auf das neue B: A ≤ₚ B. Dann ist B mindestens so schwer wie A. Die umgekehrte Richtung würde nichts über die Schwere von B aussagen.
- F4.Eine Reduktion A ≤ₚ B muss in polynomieller Zeit berechenbar sein.
Antwort: Wahr
Erklärung: Richtig. Nur eine in polynomieller Zeit berechenbare Abbildung überträgt die Komplexität korrekt. Eine exponentielle Übersetzung würde die Schwere nicht aussagekräftig weitergeben.
Typ: Wahr/Falsch
- F5.Ordne die Begriffe richtig zu.
Zuordnungen:
- Cook-Levin → SAT ist NP-vollständig (1971)
- 3-SAT → drei Literale pro Klausel
- KNF → Konjunktion von Klauseln
- Karp-Reduktion → polynomielle Abbildung A ≤ₚ B
Erklärung: Cook-Levin: SAT NP-vollständig. 3-SAT: drei Literale je Klausel. KNF: Und-Verknüpfung von Oder-Klauseln. Karp-Reduktion: polynomielle Many-One-Reduktion.
Typ: Zuordnung
- F6.Bei der Reduktion 3-SAT ≤ₚ CLIQUE: was entspricht einer erfüllenden Belegung?
Antwort: eine Clique der Größe k (Anzahl der Klauseln)
Erklärung: Jede Klausel wird zu einer Knotengruppe, Kanten verbinden verträgliche Literale verschiedener Klauseln. Eine k-Clique (k = Klauselzahl) wählt aus jeder Klausel ein verträgliches Literal und entspricht damit genau einer erfüllenden Belegung.
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Welches Problem wurde zuerst als NP-vollständig bewiesen?
Antwort: SAT (Satz von Cook-Levin)
Erklärung: SAT wurde 1971 durch den Satz von Cook-Levin als erstes Problem direkt als NP-vollständig bewiesen (über die Simulation einer nichtdeterministischen Turing-Maschine). Alle weiteren folgten per Reduktion von SAT bzw. 3-SAT.
- F2.Was ist eine Klausel in der konjunktiven Normalform (KNF)?
Antwort: eine Disjunktion (ODER) von Literalen
Erklärung: In KNF ist die Formel eine Konjunktion (UND) von Klauseln, und jede Klausel ist eine Disjunktion (ODER) von Literalen. Bei 3-SAT hat jede Klausel genau drei Literale.
- F3.Ein Problem B ist NP-vollständig, wenn B in {{1}} liegt und ein bekanntes NP-vollständiges Problem {{2}} auf B reduziert wird. SAT wurde als erstes durch den Satz von {{3}} bewiesen.
Lösungen pro Lücke:
- {{1}}: NP
- {{2}}: polynomiell / in polynomieller Zeit / poly
- {{3}}: Cook-Levin / Cook / Cook und Levin
Erklärung: NP-vollständig: in NP + NP-schwer (per polynomieller Reduktion eines bekannten NP-vollständigen Problems). SAT: Cook-Levin 1971.
Typ: Lückentext
- F4.Warum genügt es, 3-SAT auf ein neues Problem B zu reduzieren, statt alle NP-Probleme?
Antwort: weil jedes NP-Problem bereits auf 3-SAT reduzierbar ist und Reduktionen transitiv sind
Erklärung: Da jedes NP-Problem polynomiell auf 3-SAT reduzierbar ist und die polynomielle Reduktion transitiv ist, überträgt sich über 3-SAT ≤ₚ B die Schwere aller NP-Probleme auf B. Daher reicht die eine Reduktion.
- F5.Was muss man für die Korrektheit der Reduktion 3-SAT ≤ₚ CLIQUE zeigen?
Antwort: dass die Formel genau dann erfüllbar ist, wenn der Graph eine k-Clique hat (beide Richtungen)
Erklärung: Korrektheit heißt: erfüllbare Formel ⟹ k-Clique existiert, UND k-Clique ⟹ erfüllbare Belegung. Nur wenn beide Richtungen gelten, ist die Reduktion gültig.
- F6.Jemand findet einen Polynomialalgorithmus für CLIQUE. Was folgt?
Antwort: P = NP, weil CLIQUE NP-vollständig ist und damit alle NP-Probleme effizient lösbar wären
Erklärung: CLIQUE ist NP-vollständig. Ein Polynomialalgorithmus dafür würde über die Reduktionen alle NP-Probleme in Polynomialzeit lösbar machen, also P = NP. Das ist bislang weder gelungen noch widerlegt.
