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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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:
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).
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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:
A ≤_p B und ihre Richtung≤_p CLIQUEEin 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 (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?
(x₁ vee x₂ vee neg x₃) wedge (neg x₁ vee x₂ vee x₃)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.
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.B ist NP-schwer: reduziere ein bekanntes NP-vollständiges A (z.B. 3-SAT) auf B, also A ≤_p B.Die Richtung ist entscheidend: das bekannte schwere A wird auf das neue B reduziert.
≤_p CLIQUEDie 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.
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.
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.
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.
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).
Klausurfragen mit Lösungen (6)
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).
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.
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.
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
Zuordnungen:
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
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.
Klausurfragen mit Lösungen (6)
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.
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.
Lösungen pro Lücke:
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
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.
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.
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.