Polynomielle Reduktionen Flashcards
Angenommen, Algorithmus A entscheidet SAT Instanzen in T(n, m) Zeit. Dann gibt es einen Algorithmus B, der für erfüllbare SAT Instanzen in … Zeit eine erfüllende Wahrheitsbelegung konstruiert.
n · T(n, m)
Angenommen, Algorithmus A entscheidet CLIQUE in T(n) Zeit. Dann gibt es einen Algorithmus B, der für JA-Instanzen in … Zeit eine k-Clique konstruiert.
n · T(n)
Angenommen, Algorithmus A entscheidet Ham-Cycle in T(n) Zeit.
Dann gibt es einen Algorithmus B, der für JA-Instanzen
in… Zeit einen Hamiltonkreis konstruiert.
|E| · T(n)
Definition: Optimierungsproblem
Die Eingabe eines Optimierungsproblems spezifiziert eine Menge L von zulässigen Lösungen zusammen mit einer Zielfunktion f : L → N, die Kosten, Gewicht, oder Profit misst.
Das Ziel ist es, eine optimale Lösung in L zu berechnen.
In Minimierungsproblemen sollen die Kosten minimiert werden, und in Maximierungsproblemen soll der Profit maximiert werden.
Optimierungsvariante Rucksack / Knapsack (KP)
Eingabe: Natürliche Zahlen w1, . . . ,wn, p1, . . . , pn, und b
Zulässige Lösung: Menge K ⊆ {1, . . . , n} mit w(K) := Summe nach i∈K aller wi ≤ b
Ziel: Maximiere p(K) := Summe nach i∈K aller pi
Entscheidungsvariante Rucksack / Knapsack (KP)
Eingabe: Natürliche Zahlen w1, . . . ,wn, p1, . . . , pn, und b, Schranke γ
Lösung: Existiert eine Menge K ⊆ {1, . . . , n} mit w(K) := Summe nach i∈K aller wi ≤ b und p(K) ≥ γ, wobei p(K) := Summe nach i∈K aller pi
Optimierungsvariante Bin Packing (BPP)
Eingabe: Natürliche Zahlen b und w1, . . . ,wn ∈ {1, . . . , b}
Zuässige Lösung: Zahl k ∈ N und Funktion f : {1, . . . , n} → {1, . . . , k} sodass ∀i ∈ {1, . . . , k} : Summe nach j∈f−1(i)
aller wj ≤ b
Ziel: Minimiere k (= Anzahl der Kisten)
Entscheidungsvariante der Bin Packing (BPP)
Eingabe: Natürliche Zahlen b und w1, . . . ,wn ∈ {1, . . . , b}, Schranke γ
Frage: Existiert eine Zahl k ∈ N mit k ≤ γ und eine Funktion f : {1, . . . , n} → {1, . . . , k} sodass ∀i ∈ {1, . . . , k} :Summe nach j∈f −1(i) aller wj ≤ b
Optimierungsvariante Travelling Salesman (TSP)
Eingabe: Natürliche Zahlen d(i, j) für 1 ≤ i ≠ j ≤ n
Zulässige Lösung: Permutation π von 1, . . . , n
Ziel: Minimiere d(π) := Summe mit i von 1 bis n−1 von
d(π(i), π(i + 1)) + d(π(n), π(1))
Entscheidungsvariante Travelling Salesman (TSP)
Eingabe: Natürliche Zahlen d(i, j) für 1 ≤ i ≠ j ≤ n, Schranke γ
Lösung: Permutation π von 1, . . . , n mit d(π) ≤ γ, d(π) := Summe mit i von 1 bis n−1 von
d(π(i), π(i + 1)) + d(π(n), π(1))
Wenn das Entscheidungsproblem für … in polynomieller Zeit lösbar ist, so ist auch das Optimierungsproblem für … in polynomieller Zeit lösbar.
KP, TSP, Bin-Packing
Die Komplexitätsklasse EXPTIME
EXPTIME ist 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.
Definition: Es seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Dann ist L1 polynomiell reduzierbar auf L2 (mit der Notation L1 ≤p L2), wenn …
eine polynomiell berechenbare Funktion f : Σ* → Σ*
so dass für alle x ∈ Σ* gilt: x ∈ L1 ⇔ f (x) ∈ L2.
Problem: Knotenfärbung (COLORING)
Eingabe: Ein ungerichteter Graph G = (V, E); eine Zahl k ∈ N
Frage: Gibt es eine Färbung c : V → {1, . . . , k} der Knoten mit k Farben, sodass benachbarte Knoten verschiedene Farben erhalten? ∀e = {u, v} ∈ E : c(u) ≠ c(v)?
EX-COVER, COLORING ≤p SAT
SATZ
