P versus NP Flashcards
Definition: Worst Case Laufzeit t_A(n) eines Algorithmus A
maximale Laufzeitkosten auf Eingaben der Länge n bezüglich des logarithmisches Kostenmaßes der RAM.
Worst Case Laufzeit t_A(n) eines Algorithmus A ist polynomiell beschränkt, falls gilt
∃α ϵ N : t_A(n) ϵ O(n^α)
Ein Algorithmus mit polynomiell beschränkter Worst Case Laufzeit heißt
Polynomialzeitalgorithmus
SORTIEREN kann in …. Zeit gelöst werden.
polynomieller
Problem SORTIEREN
Eingabe: Zahlen a_1, …, a_n ϵ N in Binärdarstellung
Ausgabe: Die aufsteigend sortierte Folge der Eingabezahlen
Beispiele von Probleme mit polynomiellen Algorithmus lösbar
Eulerkreis Kürzester Weg Minimaler Spannbaum Maximaler Fluss Maximum Matching Primzahltest Grösste gemeinsamer Teiler
Definition: Komplexitätsklasse P
Die Klasse aller Entscheidungsprobleme, für die es einen polynomiellen Algorithmus gibt
Problem GRAPHZUSAMMENHANG
Eingabe: Ein ungerichteter Graph G=(V, E)
Ausgabe: Ist G zusammenhängend?
GRAPHZUSAMMENHANG ϵ … (Welche Komplexitätsklasse?)
P
Definition: Non-deterministische Turingmaschine (NTM)
Eine NTM verfügt über:
- ein beidseitig unbeschränktes Arbeitsband
- einen Lese/Schreibkopf
- einen Mechanismus, der die Zustandüberführungen steuert
Zustandsüberführung des NTM ist der Form:
δ ⊆ ( (Q\ {notq} ⋅ Γ) ⋅ ( Q ⋅ Γ ⋅ {L,R,N} )
Der Unterschied zwischen TM und NTM:
Zustandsüberführung ist durch eine Relation und nicht durch eine Funktion gesteuert:
δ ⊆ ( (Q\ {notq} ⋅ Γ) ⋅ ( Q ⋅ Γ ⋅ {L,R,N} )
Rechenweg einer NTM =
Konfigurationsfolge, die mit Startkonfiguration beginnt und mit Nachfolgekonfiguration fortgesetzt wird, bis eine Endkonfiguration im Zustand not q erreicht wird.
maximale Verzweigungsgrad des Berechenbaumes ist Δ :=
max{ |δ(q,a)| | q ϵ Q\ {notq}, a ϵ Γ }
Eine NTM M akzeptiert die Eingabe x ϵ Σ*, falls…
es mindestens eine Rechenweg von M gibt, der in eine Konfiguration mit akzeptierendem Zustand führt.
Die Laufzeit einer NTM M auf einer Eingabe x:
- Falls x ϵ L(M), so ist die Laufzeit T_M(x) =…
- Falls x ∉ L(M), so ist die Laufzeit T_M(x) =….
- die Länge der kürzesten akzeptierenden Rechenwegs von M auf x
- 0
Definition: Komplexitätsklasse NP
Die Klasse aller Entscheidungsprobleme, die durch eine NTM M erkannt werden, deren Worst Case Laufzeit t_M(n) polynomiell beschränkt ist.
Problem CLIQUE
Eingabe: Ein ungerichteter Graph G=(V,E); eine Zahl k
Frage: Enthält G eine Clique mit ≥ k Knoten?
CLIQUE ϵ …. (welche Komplexitätsklasse)
NP
Zertifikat Charakterisierung von NP
Eine Sprache L ⊆ Σ* liegt genau dann in NP,
wenn es einen polynomiellen Algorithmus V
und ein Polynom p mit der folgenden Eigenschaft gibt:
x ∈ L⟺ ∃y ∈ {0, 1}*, |y | ≤ p(|x|) : V akzeptiert y#x
Problem: Satisfiability (SAT)
Eingabe: Eine Boole’sche Formel φ in KNF über einer
Boole’schen Variablenmenge X = {x1, . . . , xn}
Frage: Existiert eine Wahrheitsbelegung von X, die φ erfüllt?
SAT ϵ … (Welche Komplexitätsklasse?)
NP
Problem: Independent Set (INDEP-SET)
Eingabe: Ein ungerichteter Graph G = (V, E); eine Zahl k
Frage: Enthält G eine unabhängige Menge mit ≥ k Knoten?
INDEP-SET ϵ … (Welche Komplexitätsklasse?)
NP
Problem: Vertex Cover (VC)
Eingabe: Ein ungerichteter Graph G = (V, E); eine Zahl k
Frage: Enthält G ein Vertex Cover mit ≤ k Knoten?
VC ϵ … (Welche Komplexitätsklasse?)
NP
Problem: Hamiltonkreis (Ham-Cycle)
Eingabe: Ein ungerichteter Graph G = (V, E)
Frage: Besitzt G einen Hamiltonkreis?
Problem: Travelling Salesman Problem (TSP)
Eingabe: Städte 1, . . . , n; Distanzen d(i, j); eine Zahl γ
Frage: Gibt es eine Rundreise (TSP-Tour) mit Länge höchstens γ?
Problem: Exact Cover (EX-COVER)
Eingabe: Eine endliche Menge X; Teilmengen S_1, . . . , S_m von X
Frage: Existiert eine Indexmenge I ⊆ {1, . . . , m},
sodass die Mengen Si mit i ∈ I eine Partition von X bilden?
Problem: SUBSET-SUM
Eingabe: Positive ganze Zahlen a1, . . . , an; eine ganze Zahl b
Frage: Existiert eine Indexmenge I ⊆ {1, . . . , n} mit Summe nach i ∈ I aller ai = b?
Problem: PARTITION
Eingabe: Positive ganze Zahlen a1, . . . , an; mit Summe nach i von 1 bis n = 2A
Frage: Existiert eine Indexmenge I ⊆ {1, . . . , n} mit Summe nach i∈I aller ai = A?
