VL-13: Polynomielle Reduktionen
(Berechenbarkeit und Komplexitat, WS 2019)
Gerhard Woeginger
WS 2019, RWTH
BuK/WS 2019 VL-13: Polynomielle Reduktionen 1/48
Organisatorisches
Nachste Vorlesungen:
Freitag, Dezember 13, 12:30–14:00, Audimax
Mittwoch, Dezember 18, 10:30–12:00, Aula
Webseite:
https://algo.rwth-aachen.de/Lehre/WS1920/BuK/BuK.py
BuK/WS 2019 VL-13: Polynomielle Reduktionen 2/48
Wdh.: Non-deterministische Turingmaschine (NTM)
Definition: Akzeptanzverhalten der NTM
Eine NTM M akzeptiert die Eingabe x ∈ Σ∗,falls es mindestens einen Rechenweg von M gibt,
der in eine Konfiguration mit akzeptierendem Zustand fuhrt.
q00011
q0011
q1011 reject
q111
q011 reject
q11
q21 reject
q1
q2 accept
reject
BuK/WS 2019 VL-13: Polynomielle Reduktionen 4/48
Wdh.: P und NP
Komplexitatsklassen P und NP
P ist die Klasse aller Entscheidungsprobleme,
die durch eine TM M erkannt werden,
deren Worst Case Laufzeit tM(n) polynomiell beschrankt ist.
NP ist die Klasse aller Entscheidungsprobleme,
die durch eine NTM M erkannt werden,
deren Worst Case Laufzeit tM(n) polynomiell beschrankt ist.
Satz (Zertifikat Charakterisierung von NP)
Eine Sprache L ⊆ Σ∗ liegt genau dann in NP,
wenn es einen polynomiellen deterministischen Algorithmus V
und ein Polynom p mit der folgenden Eigenschaft gibt:
x ∈ L ⇐⇒ ∃y ∈ {0, 1}∗, |y | ≤ p(|x |) : V akzeptiert y#x
BuK/WS 2019 VL-13: Polynomielle Reduktionen 5/48
Ubung
Definition (Postsches Correspondenzproblem, PCP)
Eine Instanz des PCP besteht aus einer endlichen Menge
K =
{[x1y1
], . . . ,
[xkyk
]}.
Die Frage ist, ob es eine (nicht-leere) correspondierende Folge 〈i1, . . . , in〉gibt, sodass xi1xi2 . . . xin = yi1yi2 . . . yin gilt.
Ein zweifelhafter Satz
PCP ∈ NP
Ein zweifelhafter Beweis:
Zertifikat = correspondierende Folge 〈i1, . . . , in〉Verifizierer uberpruft, ob xi1xi2 . . . xin = yi1yi2 . . . yin gilt
BuK/WS 2019 VL-13: Polynomielle Reduktionen 6/48
Wdh.: Probleme in NP
Problem: Satisfiability (SAT)
Eingabe: Eine Boole’sche Formel ϕ in CNF uber einer
Boole’schen Variablenmenge X = {x1, . . . , xn}Frage: Existiert eine Wahrheitsbelegung von X , die ϕ erfullt?
Problem: CLIQUE
Eingabe: Ein ungerichteter Graph G = (V ,E ); eine Zahl k
Frage: Enthalt G eine Clique mit ≥ k Knoten?
Problem: Hamiltonkreis (Ham-Cycle)
Eingabe: Ein ungerichteter Graph G = (V ,E )
Frage: Besitzt G einen Hamiltonkreis?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 7/48
Wdh.: Die Komplexitatslandschaft
NP
P
Graph-zusammenhang
Primzahl
SAT
Clique
Ind-Set
VC
Ham-Cycle
TSP
Partition
Subset-Sum
Ex-Cover
Warnung: Dieser Abbildung liegt die Annahme P 6= NP zu Grunde.
BuK/WS 2019 VL-13: Polynomielle Reduktionen 8/48
Wdh.: Die grosse offene Frage der Informatik
P=NP ?
Falls die Losung eines Problems einfach zu uberprufen ist,
ist es dann auch immer einfach, die Losung selbst zu entdecken?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 9/48
Vorlesung VL-13
Polynomielle Reduktionen
Die Komplexitatsklasse EXPTIME
Losung finden versus Losbarkeit entscheiden
Optimieren versus Losbarkeit entscheiden
Polynomielle Reduktionen
BuK/WS 2019 VL-13: Polynomielle Reduktionen 10/48
EXPTIME: Definition
Definition: Komplexitatsklasse EXPTIME
EXPTIME ist die Klasse aller Entscheidungsprobleme,
die durch eine (deterministische) TM M entschieden werden, deren
Worst Case Laufzeit durch 2q(n) mit einem Polynom q beschrankt ist,
Laufzeit-Beispiele: 2√n, 2n, 3n, n · 2n, n!, nn
Aber nicht: 22n
und nnn
Frage: Wie verhalten sich die Klassen P und NP zu EXPTIME?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 12/48
EXPTIME: NP ⊆ EXPTIME
Satz
NP ⊆ EXPTIME
Es sei L ∈ NPDann gibt es ein Polynom p und einen polynomiellen Algorithmus V
x ∈ L ⇐⇒ ∃y ∈ {0, 1}∗, |y | ≤ p(|x |) : V akzeptiert y#x
Wir enumerieren alle Kandidaten y ∈ {0, 1}∗ mit |y | ≤ p(|x |).
Wir testen jeden einzelnen Kandidaten mit dem Verifizierer V .
Wir akzeptieren, falls V einen der Kandidaten akzeptiert.
Anzahl der Kandidaten ≈ 2p(|x |)
Zeit pro Kandidat ≈ polynomiell in |x |+ |y |Ergo: Gesamtzeit ≈ poly(|x |) · 2p(|x |)
BuK/WS 2019 VL-13: Polynomielle Reduktionen 13/48
EXPTIME: Zwei Beispiele
Problem: Satisfiability (SAT)
Eingabe: Eine Boole’sche Formel ϕ in CNF uber der
Boole’schen Variablenmenge X = {x1, . . . , xn}Frage: Existiert eine Wahrheitsbelegung von X , die ϕ erfullt?
Problem: Hamiltonkreis (HAM-CYCLE)
Eingabe: Ein ungerichteter Graph G = (V ,E ) mit |V | = n
Frage: Besitzt G einen Hamiltonkreis?
Frage: Welche (exponentielle) Zeitkomplexitat ergibt sich aus dem
vorangehenden Beweis fur die Probleme SAT und HAM-CYCLE?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 14/48
Losung finden vs Losbarkeit entscheiden
Ein beliebiges Entscheidungsproblem in NP
Eingabe: Ein diskretes Objekt X .
Frage: Existiert fur dieses Objekt X ein Losungsobjekt Y ?
Dilemma:
Das Entscheidungsproblem beschaftigt sich nur mit der Frage,
ob ein derartiges Losungsobjekt Y existiert.
Aber eigentlich will man das Losungsobjekt Y auch genau
bestimmen, und dann damit weiter arbeiten.
Ausweg:
Ein schneller Algorithmus fur das Entscheidungsproblem liefert
(durch wiederholte Anwendung) oft auch einen schnellen
Algorithmus zum Berechnen eines expliziten Losungsobjekts
BuK/WS 2019 VL-13: Polynomielle Reduktionen 16/48
Beispiel: SAT (1)
Problem: Satisfiability (SAT)
Eingabe: Boole’sche Formel ϕ in CNF uber X = {x1, . . . , xn}Frage: Existiert eine Wahrheitsbelegung von X , die ϕ erfullt?
Wenn wir in ϕ eine Variable x := 1 setzen,
so werden alle Klauseln mit Literal x dadurch erfullt und
in allen Klauseln mit Literal x fallt dieses Literal einfach weg.
Wir erhalten wir eine kurzere CNF-Formel ϕ[x = 1].
Analog erhalten wir mit x := 0 die CNF-Formel ϕ[x = 0].
Beispiel
Fur ϕ = (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z) ∧ (¬y ∨ z) ∧ (u ∨ z)
gilt ϕ[y = 1] = (¬x ∨ ¬z) ∧ (z) ∧ (u ∨ z)
und ϕ[z = 0] = (x ∨ y) ∧ (¬y) ∧ (u)
BuK/WS 2019 VL-13: Polynomielle Reduktionen 17/48
Beispiel: SAT (2)
Wir betrachten SAT Instanzen mit n Variablen und m Klauseln.
Satz
Angenommen, Algorithmus A entscheidet SAT Instanzen in T (n,m) Zeit.
Dann gibt es einen Algorithmus B, der fur erfullbare SAT Instanzen
in n · T (n,m) Zeit eine erfullende Wahrheitsbelegung konstruiert.
Beweis:
Wir fixieren der Reihe nach die Wahrheitswerte von x1, x2, . . . , xn.
FOR i = 1, 2, . . . , n DO
Wenn ϕ[xi = 1] erfullbar, setze xi := 1 und ϕ := ϕ[xi = 1]Andernfalls setze xi := 0 und ϕ := ϕ[xi = 0]
Am Ende ergeben die fixierten Wahrheitswerte von x1, x2, . . . , xneine erfullende Wahrheitsbelegung fur ϕ
BuK/WS 2019 VL-13: Polynomielle Reduktionen 18/48
Beispiel: CLIQUE
Problem: CLIQUE
Eingabe: Ein ungerichteter Graph G = (V ,E ); eine Zahl k
Frage: Enthalt G eine Clique mit ≥ k Knoten?
Wenn wir aus G einen Knoten v und alle zu v inzidenten Kanten
wegstreichen, so erhalten wir den kleineren Graphen G − vFalls G − v eine k-Clique enthalt, so ist v irrelevant
Falls G − v keine k-Clique enthalt, so muss v im Graphen bleiben
Satz
Angenommen, Algorithmus A entscheidet CLIQUE in T (n) Zeit.
Dann gibt es einen Algorithmus B, der fur JA-Instanzen
in n · T (n) Zeit eine k-Clique konstruiert.
BuK/WS 2019 VL-13: Polynomielle Reduktionen 19/48
Beispiel: Hamiltonkreis
Problem: Hamiltonkreis (Ham-Cycle)
Eingabe: Ein ungerichteter Graph G = (V ,E )
Frage: Besitzt G einen Hamiltonkreis?
Wenn wir aus G eine Kante e wegstreichen, so erhalten wir den
kleineren Graphen G − eFalls G − e einen Hamiltonkreis enthalt, so ist e irrelevant
Falls G − e keinen Hamiltonkreis enthalt, so muss e bleiben
Satz
Angenommen, Algorithmus A entscheidet Ham-Cycle in T (n) Zeit.
Dann gibt es einen Algorithmus B, der fur JA-Instanzen
in |E | · T (n) Zeit einen Hamiltonkreis konstruiert.
BuK/WS 2019 VL-13: Polynomielle Reduktionen 20/48
Optimieren vs Entscheiden
Definition: Optimierungsproblem
Die Eingabe eines Optimierungsproblems spezifiziert (implizit oder
explizit) eine Menge L von zulassigen Losungen zusammen mit einer
Zielfunktion f : L → N, die Kosten, Gewicht, oder Profit misst.
Das Ziel ist es, eine optimale Losung in L zu berechnen:
In Minimierungsproblemen sollen die Kosten minimiert werden.
In Maximierungsproblemen soll der Profit maximiert werden.
Dilemma:
Die Klassen P und NP enthalten keine Optimierungsprobleme,
sondern nur Entscheidungsprobleme
Ausweg:
Jedes Optimierungsproblem kann in ein “sehr ahnliches”
Entscheidungsproblem umformuliert werden
BuK/WS 2019 VL-13: Polynomielle Reduktionen 22/48
Beispiel: Travelling Salesman
Beim Travelling Salesman Problem sind Stadte 1, . . . , n gegeben,
zusammen mit Distanzen d(i , j) fur 1 ≤ i 6= j ≤ nGesucht ist eine moglichst kurze Rundreise (Hamiltonkreis; Tour)
durch alle Stadte
Problem: Travelling Salesman (TSP)
Eingabe: Naturliche Zahlen d(i , j) fur 1 ≤ i 6= j ≤ nZulassige Losung: Permutation π von 1, . . . , n
Ziel: Minimiere d(π) :=
n−1∑i=1
d(π(i), π(i + 1)) + d(π(n), π(1))
Entscheidungsproblem:
Die Eingabe enthalt zusatzlich eine Schranke γ
Frage: Existiert eine zulassige Losung mit Lange d(π) ≤ γ?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 23/48
Beispiel: Bin Packing
Beim Bin Packing sollen n Objekte 1, . . . , n mit Gewichten w1, . . . ,wnauf moglichst wenige Kisten mit Gewichtslimit B verteilt werden.
Problem: Bin Packing (BPP)
Eingabe: Eine ganze Zahl B und Zahlen w1, . . . ,wn ∈ {1, . . . ,B}Zulassige Losung: Partition von 1, . . . , n in Teilmengen T1, . . . ,Tk ,
sodass w(Tj) ≤ B fur alle 1 ≤ j ≤ k gilt.
Ziel: Minimiere die Anzahl k der Teilmengen.
Entscheidungsproblem:
Die Eingabe enthalt zusatzlich eine Schranke γ fur die Anzahl der
Kisten.
Frage: Existiert eine zulassige Losung T1, . . . ,Tk mit k ≤ γ?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 24/48
Beispiel: Knapsack
Beim Knapsack Problem (KP; Rucksackproblem) sind n Objekte mit
Gewichten w1, . . . ,wn und Profiten p1, . . . , pn gegeben
Ausserdem ist eine Gewichtsschranke w gegeben
Wir suchen eine Teilmenge K der Objekte, die in einen Rucksack mit
Gewichtsschranke w passt und die den Gesamtprofit maximiert
Problem: Knapsack (KP)
Eingabe: Naturliche Zahlen w1, . . . ,wn, p1, . . . , pn, und b
Zulassige Losung: Menge K ⊆ {1, . . . , n} mit w(K ) :=∑i∈K wi ≤ w
Ziel: Maximiere p(K ) :=∑i∈K pi
Entscheidungsproblem:
Die Eingabe enthalt zusatzlich eine Schranke γ fur den Profit
Frage: Existiert eine zulassige Losung K mit p(K ) ≥ γ?
BuK/WS 2019 VL-13: Polynomielle Reduktionen 25/48
Allgemein: Optimieren vs Entscheiden
Fur ein Optimierungsproblem mit einer Menge L von zulassigen Losungen
und einer Kostenfunktion f : L → N definieren wir das entsprechende
Entscheidungsproblem:
Eingabe: Wie im Optimierungsproblem; plus Schranke γ ∈ N
Frage: Existiert eine zulassige Losung x ∈ Lmit f (x) ≥ γ (fur Maximierungsprobleme) respektive
mit f (x) ≤ γ (fur Minimierungsprobleme)?
Mit Hilfe eines Algorithmus, der das Optimierungsproblem lost,
kann man immer das entsprechende Entscheidungsproblem losen.
(Wie?)
Mit Hilfe eines Algorithmus, der das Entscheidungsproblem lost,
kann man den optimalen Zielfunktionswert bestimmen
(und oft auch die dazugehorende optimale Losung finden).
BuK/WS 2019 VL-13: Polynomielle Reduktionen 26/48
Beispiel: Knapsack (1)
Eingabe: Naturliche Zahlen w1, . . . ,wn, p1, . . . , pn; w ; γ
Zulassig: Menge K ⊆ {1, . . . , n} mit w(K ) ≤ w
Optimierung: Berechne zulassiges K mit maximalem p(K )Entscheidung: Existiert zulassiges K mit p(K ) ≥ γ?
Satz
Wenn Knapsack-Entscheidung in T (|I |) Zeit losbar ist,
so ist Knapsack-Optimierung in poly(|I |) · T (|I |) Zeit losbar.
Beweis: Aus einem schnellen Algorithmus A furs Entscheidungsproblem
konstruieren wir zuerst einen schnellen Algorithmus B,
der den optimalen Zielfunktionswert bestimmt
und dann einen schnellen Algorithmus C ,
der eine optimale zulassige Losung bestimmt
BuK/WS 2019 VL-13: Polynomielle Reduktionen 27/48
Beispiel: Knapsack (2)
Algorithmus B fur (Phase 1)
Wir fuhren eine Binare Suche mit den folgenden Parametern durch:
Der minimal mogliche Profit ist 0.
Der maximal mogliche Profit ist P :=
n∑i=1
pi .
Wir finden den optimalen Zielfunktionswert durch Binare Suche uber
dem Wertebereich {0, . . . ,P}.In jeder Iteration verwenden wir den polynomiellen Algorithmus A
(fur das Entscheidungsproblem), der uns mitteilt, in welcher Halfte
des verbleibenden Wertebereichs wir weitersuchen mussen
Die Anzahl der Iterationen der Binarsuche ist dlog(P + 1)e.
BuK/WS 2019 VL-13: Polynomielle Reduktionen 28/48
Beispiel: Knapsack (3)
Algorithmus B besteht aus ≤ dlog(P + 1)e Aufrufen von
Algorithmus A in der binaren Suche.
Also ist die Gesamtlaufzeit von Algorithmus B durch
dlog(P + 1)e · T (|I |) beschrankt.
Die Eingabelange |I | der Knapsack-Instanz I betragt
|I | ≥n∑i=1
log(pi + 1) = log(
n∏i=1
(pi + 1))
≥ log(
n∑i=1
(pi + 1)) ≈ log(P + 1)
Die Gesamtlaufzeit von Algorithmus B ist durch |I | · T (|I |) beschrankt.
BuK/WS 2019 VL-13: Polynomielle Reduktionen 29/48
Beispiel: Knapsack (4)
Aus Algorithmus B konstruieren wir nun noch den Algorithmus C , der die
optimale zulassige Losung bestimmt:
Algorithmus C
1 K:= –1,...,n˝;
2 opt:= Algo˙B(K);
3 for i:= 1 to n do
4 if Algo˙B(K-–i˝)==opt then K:= K-–i˝;
5 return K
Algorithmus C besteht im wesentlichen aus n + 1 Aufrufen des
polynomiellen Algorithmus B
Also ist die Gesamtlaufzeit von Algorithmus C durch n · |I | · T (|I |)und folglich durch poly(|I |) · T (|I |) beschrankt
BuK/WS 2019 VL-13: Polynomielle Reduktionen 30/48
Zur Erinnerung: Eine alte Seite aus Vorlesung VL-06
Definition
Es seien L1 und L2 zwei Sprachen uber einem Alphabet Σ.
Dann ist L1 auf L2 reduzierbar (mit der Notation L1 ≤ L2),
wenn eine berechenbare Funktion f : Σ∗ → Σ∗ existiert,
so dass fur alle x ∈ Σ∗ gilt: x ∈ L1 ⇔ f (x) ∈ L2.
{0, 1}∗{0, 1}∗
L2L1
f
BuK/WS 2019 VL-13: Polynomielle Reduktionen 32/48
Polynomielle Reduktionen (1)
Definition
Es seien L1 und L2 zwei Sprachen uber einem Alphabet Σ.
Dann ist L1 polynomiell reduzierbar auf L2 (mit der Notation L1 ≤p L2),
wenn eine polynomiell berechenbare Funktion f : Σ∗ → Σ∗ existiert,
so dass fur alle x ∈ Σ∗ gilt: x ∈ L1 ⇔ f (x) ∈ L2.
{0, 1}∗{0, 1}∗
L2L1
f
BuK/WS 2019 VL-13: Polynomielle Reduktionen 33/48
Polynomielle Reduktionen (2)
Satz
Falls L1 ≤p L2 und falls L2 ∈ P, so gilt L1 ∈ P.
Beweis:
Die Reduktion f hat eine polynomielle Laufzeitschranke p(·)Ein Algorithmus A2 entscheidet L2 mit einer polynomiellen
Laufzeitschranke q(·)
Wir konstruieren einen Algorithmus A1, der L1 entscheidet:
Schritt 1: Berechne f (x)Schritt 2: Simuliere Algorithmus A2 auf f (x)Schritt 3: Akzeptiere x , genau dann wenn A2 akzeptiert
Schritt 1 hat Laufzeit p(|x |) und
Schritt 2 hat Laufzeit q(|f (x)|) ≤ q(p(|x |) + |x |)
BuK/WS 2019 VL-13: Polynomielle Reduktionen 34/48
Polynomielle Reduktionen (3)
Algorithmus A1 fur L1
xReduktion
Algorithmus
A2 fur L2
x ∈ L1
Y/N
f (x) f (x)∈L2
Y/N
BuK/WS 2019 VL-13: Polynomielle Reduktionen 35/48
COLORING ≤p SAT
Problem: Knotenfarbung / COLORING
Eingabe: Ein ungerichteter Graph G = (V ,E ); eine Zahl k ∈ NFrage: Gibt es eine Farbung c : V → {1, . . . , k} der Knoten
mit k Farben, sodass benachbarte Knoten verschiedene Farben
erhalten? ∀e = {u, v} ∈ E : c(u) 6= c(v)?
Problem: Satisfiability (SAT)
Eingabe: Boole’sche Formel ϕ in CNF uber der Variablenmenge X
Frage: Existiert eine Wahrheitsbelegung von X , die ϕ erfullt?
Satz
COLORING ≤p SAT
BuK/WS 2019 VL-13: Polynomielle Reduktionen 37/48
COLORING ≤p SAT: Die Reduktion
Die Boole’schen Variablen
Fur jeden Knoten v ∈ V und fur jede Farbe i ∈ {1, . . . , k}fuhren wir eine Boole’sche Variable x iv ein.
Die Klauseln
Fur jeden Knoten v ∈ Vverwenden wir die Klausel (x1v + x2v + . . .+ xkv )
Fur jede Kante {u, v} ∈ E und jede Farbe i ∈ {1, . . . , k}verwenden wir die Klausel (x iu + x iv )
Anzahl der Variablen = k |V |Anzahl der Klauseln = |V |+ k |E |Gesamtlange der Formel = k |V |+ 2k |E | ∈ O(k |V |2)
BuK/WS 2019 VL-13: Polynomielle Reduktionen 39/48
COLORING ≤p SAT: Korrektheit (1)
Graph G hat k-Farbung ⇒ Formel ϕ ist erfullbar
Es sei c eine k-Farbung fur G
Fur jeden Knoten v mit c(v) = i setzen wir x iv = 1.
Alle anderen Variablen setzen wir auf 0.
Fur jeden Knoten v ∈ V ist (x1v + x2v + . . .+ xkv ) erfullt
Fur {u, v} ∈ E und i ∈ {1, . . . , k} ist (x iu + x iv ) erfullt
Andernfalls hatten beide Knoten u und v die selbe Farbe i .
Ergo: Diese Wahrheitsbelegung erfullt die Formel ϕ
BuK/WS 2019 VL-13: Polynomielle Reduktionen 40/48
COLORING ≤p SAT: Korrektheit (2)
Formel ϕ ist erfullbar ⇒ Graph G hat k-Farbung
Wir betrachten eine beliebige erfullende Belegung fur ϕ
Wegen der Klausel (x1v + x2v + . . .+ xkv ) gibt es fur jeden Knoten v
mindestens eine Farbe i mit x iv = 1
Fur jeden Knoten wahlen wir eine beliebige derartige Farbe aus
Wir behaupten: c(u) 6= c(v) gilt fur jede Kante {u, v} ∈ EBeweis: Falls c(u) = c(v) = i , dann gilt x iu = x iv = 1. Dann ware
aber die Klausel (x iu + x iv ) verletzt
BuK/WS 2019 VL-13: Polynomielle Reduktionen 41/48
COLORING ≤p SAT: Konsequenzen
Aus unserer Reduktion COLORING ≤p SAT folgt:
Folgerung 1
Wenn SAT einen polynomiellen Algorithmus hat,
so hat auch COLORING einen polynomiellen Algorithmus.
Folgerung 2 (logisch aquivalent zu Folgerung 1)
Wenn COLORING keinen polynomiellen Algorithmus hat,
so hat auch SAT keinen polynomiellen Algorithmus.
BuK/WS 2019 VL-13: Polynomielle Reduktionen 42/48
Ubung: Ex-Cover ≤p SAT
Problem: Exact Cover (Ex-Cover)
Eingabe: Eine endliche Menge X ; Teilmengen S1, . . . ,Sm von X
Frage: Existiert eine Indexmenge I ⊆ {1, . . . ,m},sodass die Mengen Si mit i ∈ I eine Partition von X bilden?
Ubung
Zeigen Sie: Ex-Cover ≤p SAT
BuK/WS 2019 VL-13: Polynomielle Reduktionen 43/48
Vertex Cover ≤p SAT
Problem: Vertex Cover (VC)
Eingabe: Ein ungerichteter Graph G = (V ,E ); eine Zahl k ∈ NFrage: Enthalt G ein Vertex Cover mit ≤ k Knoten?
Vertex Cover S ⊆ V enthalt mindestens einen Endpunkt von jeder Kante
Problem: Satisfiability (SAT)
Eingabe: Boole’sche Formel ϕ in CNF uber der Variablenmenge X
Frage: Existiert eine Wahrheitsbelegung von X , die ϕ erfullt?
Satz
Vertex Cover ≤p SAT
BuK/WS 2019 VL-13: Polynomielle Reduktionen 45/48
Vertex Cover ≤p SAT: Eine zweifelhafte Reduktion
Die Boole’schen Variablen
Fur jeden Knoten v ∈ Vfuhren wir eine Boole’sche Variable xv ein.
(Variable xv ist TRUE) ⇐⇒ (Knoten v ist im Vertex Cover)
Die Klauseln
Fur jede Kante {u, v} ∈ Everwenden wir die Klausel (xu + xv )
Fur jede (k + 1)-elementige Teilmenge S ⊆ Vverwenden wir die Klausel
∨v∈Sxv
Anzahl der Variablen = |V |Anzahl der Klauseln ≈ |V |k+1 (??????????)
BuK/WS 2019 VL-13: Polynomielle Reduktionen 46/48
Vertex Cover ≤p SAT: Eine korrekte Reduktion
Die Boole’schen Variablen
Fur jeden Knoten v ∈ V und fur jede Zahl i ∈ {1, 2, . . . , k}fuhren wir eine Boole’sche Variable x iv ein.
(Variable x iv ist TRUE) ⇐⇒ (v ist der i-te Knoten im Vertex Cover)
Die Klauseln
Fur jede Kante {u, v} ∈ Everwenden wir die Klausel (
∨1≤i≤k
x iu ∨∨1≤i≤k
x iv )
Fur jede Zahl i ∈ {1, 2, . . . , k} und je zwei Knoten u, v ∈ V mit u 6= vverwenden wir die Klausel (x iv + x iu)
Anzahl der Variablen = k |V |Anzahl der Klauseln ≈ |E |+ k |V |2
BuK/WS 2019 VL-13: Polynomielle Reduktionen 47/48