Satz von Cook und Levin Flashcards
Definition: NP-schwer
Ein Problem L heisst NP-schwer, falls gilt:
∀L’ ∈ NP : L’ ≤p L
Definition: NP-vollständig
Ein Problem L heisst NP-vollständig, falls gilt:
L ∈ NP, und
L ist NP-schwer.
Satz (Cook & Levin)
SAT ist NP-vollständig.
Die Variablen in der Formel ϕ
Q(t, q) für t ∈ {0, . . . , p(n)} und q ∈ Q
H(t, j) für t, j ∈ {0, . . . , p(n)}
B(t, j, a) für t, j ∈ {0, . . . , p(n)} und a ∈ Γ
t -Zeitpunkt, Q - Zustand, j- Bandposition, a- geschriebenes Zeichen
Problem: 3-SAT
Eingabe: Eine Boole’sche Formel ϕ in 3-CNF
Frage: Besitzt ϕ eine erfüllende Belegung?
SAT ≤p 3-SAT
Satz
3-SAT ist NP-vollständig.
Satz
Beweisskizze für Vertex Cover ist NP-vollständig.
Wir zeigen INDEP-SET ≤p Vertex Cover
Setze V’’ = V’ und E’’ = E’ und k’’ = |V’| − k’
Problem: ∆-TSP
Eingabe: Städte 1, . . . , n; symmetrische Distanzen d(i, j) mit Dreiecksungleichung d(i, j) ≤ d(i, k) + d(k, j); eine Zahl γ
Frage: Gibt es eine Rundreise (TSP-Tour) mit Länge höchstens γ?
Problem: {1, 2}-TSP
Eingabe: Städte 1, . . . , n; symmetrische Distanzen d(i, j) ∈ {1, 2}; eine Zahl γ
Frage: Gibt es eine Rundreise (TSP-Tour) mit Länge höchstens γ?
Gute Beschreibungen von ungerichteten Graphen G = (V, E) sind
Adjazenzlisten mit Länge l_1(G) = O(|E| log |V|)
Adjazenzmatrizen mit Länge l_2(G) = O(|V|^2)
Definition: Number
Für eine Instanz I eines Entscheidungsproblems bezeichnen wir mit Number(I) den Wert der grössten in I vorkommenden Zahl.
Definition: Pseudo-polynomielle Zeit
Ein Algorithmus A löst ein Problem X in pseudo-polynomieller Zeit, falls die Laufzeit von A auf Instanzen I von X polynomiell in |I| und Number(I) beschränkt ist.
Die Probleme … sind pseudo-polynomiell lösbar.
SUBSET-SUM, PARTITION und Rucksack
Definition: Stark NP-schwer
Ein Entscheidungsproblem X ist stark NP-schwer,
wenn es ein Polynom q : N → N gibt, sodass die Restriktion Xq von X auf Instanzen I mit Number(I) ≤ q(|I|) NP-schwer ist.
Problem: THREE-PARTITION
Eingabe: Positive ganze Zahlen a1, . . . , an, b1, . . . , bn, und c1, . . . , cn mit Summe nach i von 1 bis n
(ai + bi + ci) = nS
Frage: Gibt es zwei Permutationen α, β von 1, . . . , n,
sodass aα(i) + bβ(i) + ci = S für 1 ≤ i ≤ n gilt?
Die Probleme…. sind stark NP schwer
THREE-PARTITION und Bin Packing
Definition: Klasse coNP
Ein Entscheidungsproblem X ⊆ Σ* liegt in coNP,
wenn für jedes Wort x ∉ X ein polynomiell langes Zertifikat y existiert, das (zusammen mit x) in polynomieller Zeit verifiziert werden kann.
Problem: Unsatisfiability (UNSAT)
Eingabe: Eine Boole’sche Formel ϕ in CNF über der
Boole’schen Variablenmenge X = {x1, . . . , xn}
Frage: Gibt es keine Wahrheitsbelegung für X, die ϕ erfüllt?
Problem: TAUTOLOGY
Eingabe: Eine Boole’sche Formel ϕ in DNF über der
Boole’schen Variablenmenge X = {x1, . . . , xn}
Frage: Wird ϕ von allen Wahrheitsbelegungen von X erfüllt?
Problem: Lineare Programmierung (LP)
Eingabe: Eine reelle m × n Matrix A; Vektoren b ∈ R^m und c ∈ R^n; eine Schranke γ ∈ R
Frage: Existiert ein Vektor x ∈ R^n, der Ax ≤ b und x ≥ 0 erfüllt, und dessen Zielfunktionswert cx ≥ γ ist?
Satz von Khachiyan
LP liegt in P.
Ein Entscheidungsproblem X ist coNP-vollständig,
wenn X ∈ coNP und alle Y ∈ coNP polynomiell auf X reduzierbar sind
coNP-vollständige Probleme sind ….
Non-Ham-Cycle, UNSAT und TAUTOLOGY
