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.
Bedeutung von SAT
- Fur SAT gibt es mächtige heuristische Algorithmen
(können.
→ Daher ist Sat ein beliebtes Problem um andere Probleme
darauf zu reduzieren (Lösung durch Reduktion). - Andererseits wird Sat fur allgemeine Instanzen als
nicht-handhabbar angesehen (Sat ist NP-vollständig“,
→ Daher ist Sat ein beliebtes Problem, das auf andere
Probleme reduziert wird, um deren Nicht-Handhabbarkeit zu zeigen
Grundlegende Reduktionsstrategien:
Einfache Aquivalenz:
* Independent Set ≡P Vertex Cover.
Spezieller Fall auf allgemeinen Fall:
*Vertex Cover ≤P Set Cover.
Kodierung mit Gadgets:
*3-Sat ≤P Independent Set
Optimierungsprobleme
Ja/Nein-Problem: Existiert ein Vertex Cover der Größe ≤ k?
Optimierungsproblem: Finde kleinstes Vertex Cover.
Klar:
Ja/Nein-Problem kann mit dem Optimierungsproblem gelöst werden.
Berechne kleinstes Vertex Cover C und antworte ”
Ja“ falls
|C| ≤ k ist.
Umgekehrte Richtung: Löse Optimierungsproblem mittels (mehrmaligem) Lösen des Ja/Nein-Problems.
NP-Probleme
NP-Probleme: Ein Ja/Nein-Problem ist ein NP-Problem, falls wir Ja-Instanzen mit Hilfe eines Zertifikats effizient überprüfen können.
Zertifikat: Ein Zertifikat t fur einen Input x ist ein beliebiger String dessen Länge polynomiell in der Länge von x beschränkt ist, das heißt |t| ≤ p(|x|) gilt fur ein Polynom p.
Zertifizierer: Einen Polynomialzeitalgorithmus C(x, t), der Ja-Instanzen x mit Hilfe von Zertifikaten t uberprüft, nennt man Zertifizierer.
Anmerkung zur Notation: NP steht fur ¨
”nicht-deterministisch polynomielle“ Zeit.
Hamiltonkreisproblem
HAM-CYCLE: Gegeben sei ein ungerichteter Graph G. Existiert ein Kreis C in G der alle Knoten von G genau einmal enthält?
So ein Kreis wird als Hamiltonkreis bezeichnet.
Zertifikat: Eine Hamiltonkreis.
Zertifizierer: Uberprüfe, ob der Hamiltonkreis jeden Knoten in V genau einmal enthält und dass es eine Kante zwischen jedem Paar von direkt aufeinander folgenden Knoten in dem Hamiltonkreis und
auch vom ersten zum letzten Knoten gibt.
P, NP
P: Ja/Nein-Probleme, fur die polynomielle Algorithmen existieren.
NP: Ja/Nein-Probleme, fur die polynomielle Zertifizierer existieren.
Es gilt: P ⊆ NP.
NP-Schwer
Definition: Ein Ja/Nein-Problem Y ist NP-schwer, falls fur jedes Problem X in NP gilt, dass X ≤p Y.
Das heißt, jedes NP-Problem X kann in Polynomialzeit auf Y reduziert werden.
NP-schwere Probleme sind also gewissermaßen ”
mindestens so schwer“ wie alle Probleme in NP.
NP-Vollständigkeit
Definition: Ein Problem Y ist NP-vollst¨andig, falls es sowohl in NP
liegt als auch NP-schwer ist.
Die NP-vollständigen Probleme sind also gewissermaßen die
”schwersten“ Probleme in NP.
Nach dieser Definition können nur Ja/Nein-Probleme
NP-vollständig sein.
NP-Vollständigkeit nachweisen
Anmerkung: Sobald wir ein erstes Problem als NP-vollständig nachgewiesen haben, fallen die anderen wie Dominosteine.
Rezept um die NP-Vollständigkeit eines Problems Y nachzuweisen:
Schritt 1. Zeige dass Y in NP ist.
Schritt 2. Wähle ein NP-vollständiges Problem X.
Schritt 3. Beweise, dass X ≤p Y .
Rechtfertigung: Wenn X ein NP-vollständiges Problem ist und Y ein Problem in NP mit der Eigenschaft X ≤p Y , dann ist Y NP-vollständig.
Anwendung auf Optimierungsprobleme
NP-Vollständigkeit ist nur fur Ja/Nein-Probleme definiert.
NP-Schwere kann aber in folgender Weise auch auf funktionale Probleme und Optimierungsprobleme angewandt werden.
Intervalcoloring Laufzeit
O(n*logn)
Gewichtetes Set auf Baumen Laufzeit
O(n)
Independent Set auf Baumen
O(n)
Branch and Bound Best-first:
Es wird jeweils ein Teilproblem mit der besten dualen
Schranke (also der größten oberen Schranke) ausgewählt.
Dadurch wird immer die kleinstmögliche Anzahl an
Teilproblemen abgearbeitet
Branch and Bound Depth-first:
Es wird jeweils ein zuletzt erzeugtes Teilproblem weiter
bearbeitet (vergleiche Tiefensuche bei der Durchmusterung von Graphen).
Gewichtetes Interval Scheduling dynamish
O(n*logn)
Rücksackproblem Laufzeit
branch and bound: O(2^n)
dynamisch: O(nG)
Bellman kürzeste pfade laufzeit
O(n*m)
