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
Zwei Graphen G1 = (V1, E1) und G2 = (V2, E2) sind isomorph, wenn ..
es eine Bijektion f : V1 → V2 gibt,
die Adjazenz und Nicht-Adjazenz erhält.
GRAPH-ISOMORPHUS liegt in
NP.
GRAPH-ISOMORPHUS auf Graphen mit n Knoten
kann in Zeit gelöst werden (wobei p ein Polynom ist)
2^p(log n)
Exponential Time Hypothesis (ETH)
Es existiert eine reelle Zahl δ > 0,
sodass kein Algorithmus 3-SAT in Zeit O(2^δn) löst.
Definition
Ein Entscheidungsproblem X ⊆ Σ* heisst NP intermediate, wenn…
L ∈ NP und wenn sowohl L ∉ P als auch L ∉ NPC gilt.
Komplexitätsklasse (N)PSPACE
PSPACE ist die Klasse aller Entscheidungsprobleme,
die durch eine (N)DTM M entschieden werden, deren Worst Case Speicherplatzbedarf durch q(n) mit einem Polynom q beschränkt ist.
Satz von Savitch
PSPACE = NPSPACE
Problem: QUANTIFIED-SAT (Q-SAT) liegt in PSPACE
Eingabe: Eine Boole’sche Formel ϕ in CNF über der
Boole’schen Variablenmenge {x1, . . . , xn, y1, . . . , yn}
Frage: ∃x1 ∀y1 ∃x2 ∀y2 ∃x3 ∀y3 · · · · · · ∃xn ∀yn ϕ
Definition: Komplexitätsklasse EXPTIME
Die Klasse aller Entscheidungsprobleme,
die durch eine DTM M entschieden werden, deren Worst Case Laufzeit durch 2^q(n) mit einem Polynom q beschränkt ist.
Das k-Schritt-HALTEPROBLEM liegt in EXPTIME.
Eingabe: Eine deterministische Turingmachine M; eine ganze Zahl k
Frage: Wenn M mit leerem Band gestartet wird, hält M dann nach höchstens k Schritten an?
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
Satz
