Polynomialzeitreduktion Flashcards
Effizient lösbare Probleme
Wir bezeichnen ein Problem als effizient lösbar, wenn es in Polynomialzeit gelöst werden kann. Fur ein solches Problem ¨
existiert ein Algorithmus mit einer Laufzeit O(n^c)
n = Eingabegröße (z.B. in Bits)
c = konstanter Exponent
Effizient lösbare Probleme werden auch als handhabbar (tractable)
bezeichnet.
P or not P?
Ziel: Klassifiziere Probleme in solche, die in Polynomialzeit gelöst werden können und in solche, die nicht in Polynomialzeit gelöst werden können.
Ja/Nein-Problem (decision problem):
Ein Ja/Nein-Problem ist ein Problem, fur das die Lösung eine Ja- oder Nein-Antwort ist.
Im Gegensatz dazu wird bei funktionalen Problemen oder
Optimierungsproblemen eine Lösung (Lösungsmenge) oder
mehr als ein Bit retourniert.
Beispiel:
Gibt es fur einen gewichteten Graphen
einen Spannbaum mit Kosten ≤ k? Das kann mit Ja oder
Nein beantwortet werden
Polynomialzeitreduktionen
Informell: Kann X polynomiell auf Y reduziert werden, und wir können Y effizient lösen, dann können wir auch X effizient lösen.
Wir reduzieren dazu eine Instanz x von X auf eine Instanz y vom Y , dann lösen wir y. Ist y eine Ja-Instanz von Y , dann ist x auch eine Ja-Instanz von X.
Funktionales Problem:
Finde in einem gewichteten Graphen
einen Spannbaum mit Kosten ≤ k.
Optimierungsproblem:
Finde in einem gewichteten Graphen
einen Spannbaum mit minimalen Kosten (MST).
Aquivalenz:
X ≤ Y und Y ≤ X, dann schreiben wir
X ≡ Y .
Transitivität
Ist X ≤ Y und Y ≤ Z, dann folgt daraus X ≤ Z
Independent Set
Ein Independent Set eines Graphen G = (V, E)
ist eine Teilmenge S ⊆ V , in der es keine zwei adjazenten Knoten gibt.
INDEPENDENT SET: Gegeben sei ein Graph G = (V, E) und eine ganze Zahl k. Gibt es ein Independent Set S, sodass |S| ≥ k gilt?
Vertex Cover
Ein Vertex Cover eines Graphen G = (V, E) ist eine
Menge S ⊆ V , sodass jede Kante des Graphen zu mindestens
einem Knoten aus S inzident ist.
VERTEX COVER: Gegeben sei ein Graph G = (V, E) und eine ganze Zahl k. Gibt es ein Vertex Cover S von G, sodass |S| ≤ k?
Konversionslemma:
Sei G = (V, E) ein Graph und S ⊆ V und
C = V − S. S ist ein Independent Set von G genau dann wenn C ein Vertex Cover von G ist.
Nicht-Blockierer:
NICHT-BLOCKIERER: Gegeben ist ein Graph G = (V, E) mit
reellwertigen Kantengewichten ce = cuv = cvu fur e = (u, v) ∈ E. Ein Nicht-Blockierer ist eine Teilmenge der Kanten N ⊆ E, sodass es fur alle Knotenpaare u, v ∈ V einen u-v-Pfad in G gibt, der keine Kante aus N enthält.
Ein maximaler Nicht-Blockierer ist ein Nicht-Blockierer mit größten Kosten.
MNB: Gegeben ist ein gewichteter Graph G und eine Zahl k.
Besitzt G einen Nicht-Blockierer mit Kosten ≥ k?
Konversionslemma Nicht-Blockierer:
Sei G = (V, E) ein gewichteter Graph, N ⊆ E
und T = E − N. Dann ist N ein maximaler Nicht-Blockierer genau dann wenn T ein minimaler Spannbaum ist.
Set Cover
Gegeben sei eine Menge U von Elementen und eine
Menge S = {S1, S2, . . . , Sm} von Teilmengen von U. Ein Set Cover ist eine Teilmenge C ⊆ S, also eine Menge von Mengen, deren Vereinigung U entspricht. C ist ein Set Cover von S.
SET COVER: Gegeben sei eine Menge U von Elementen, eine
Menge S = {S1, S2, . . . , Sm} von Teilmengen von U und eine ganze Zahl k. Existiert eine Teilmenge C ⊆ S mit |C| ≤ k, sodass die Vereinigung von C gleich U ist?
Nicht jede Set Cover Instanz kann durch die Reduktion von Vertex Cover entstehen.
Daher sprechen wir hier von einer ”Reduktion eines Spezialfalls auf den allgemeinen Fall“.
Das Erfullbarkeitsproblem (SAT)
SAT (satisfiability): Gegeben ist eine KNF-Formel Φ. Gibt es eine Wahrheitsbelegung, die Φ erfüllt?
3-SAT: Sat, bei dem jede Klausel genau 3 Literale enthält.
Jedes Literal muss sich auf eine unterschiedliche Variable beziehen.
