Satz von Cook und Levin

Question 1

Definition: NP-schwer

Answer 1

Ein Problem L heisst NP-schwer, falls gilt:

∀L’ ∈ NP : L’ ≤p L

Question 2

Definition: NP-vollständig

Answer 2

Ein Problem L heisst NP-vollständig, falls gilt:
L ∈ NP, und
L ist NP-schwer.

Question 3

Satz (Cook & Levin)

Answer 3

SAT ist NP-vollständig.

Question 4

Die Variablen in der Formel ϕ

Answer 4

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

Question 5

Problem: 3-SAT

Answer 5

Eingabe: Eine Boole’sche Formel ϕ in 3-CNF
Frage: Besitzt ϕ eine erfüllende Belegung?

Question 6

SAT ≤p 3-SAT

Answer 6

Satz

Question 7

3-SAT ist NP-vollständig.

Answer 7

Satz

Question 8

Beweisskizze für Vertex Cover ist NP-vollständig.

Answer 8

Wir zeigen INDEP-SET ≤p Vertex Cover

Setze V’’ = V’ und E’’ = E’ und k’’ = |V’| − k’

Question 9

Problem: ∆-TSP

Answer 9

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 γ?

Question 10

Problem: {1, 2}-TSP

Answer 10

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 γ?

Question 11

Gute Beschreibungen von ungerichteten Graphen G = (V, E) sind

Answer 11

Adjazenzlisten mit Länge l_1(G) = O(|E| log |V|)

Adjazenzmatrizen mit Länge l_2(G) = O(|V|^2)

Question 12

Definition: Number

Answer 12

Für eine Instanz I eines Entscheidungsproblems bezeichnen wir mit Number(I) den Wert der grössten in I vorkommenden Zahl.

Question 13

Definition: Pseudo-polynomielle Zeit

Answer 13

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.

Question 14

Die Probleme … sind pseudo-polynomiell lösbar.

Answer 14

SUBSET-SUM, PARTITION und Rucksack

Question 15

Definition: Stark NP-schwer

Answer 15

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.

Question 16

Problem: THREE-PARTITION

Answer 16

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?

Question 17

Die Probleme…. sind stark NP schwer

Answer 17

THREE-PARTITION und Bin Packing

Question 18

Definition: Klasse coNP

Answer 18

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.

Question 19

Problem: Unsatisfiability (UNSAT)

Answer 19

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?

Question 20

Problem: TAUTOLOGY

Answer 20

Eingabe: Eine Boole’sche Formel ϕ in DNF über der
Boole’schen Variablenmenge X = {x1, . . . , xn}
Frage: Wird ϕ von allen Wahrheitsbelegungen von X erfüllt?

Question 21

Problem: Lineare Programmierung (LP)

Answer 21

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?

Question 22

Satz von Khachiyan

Answer 22

LP liegt in P.

Question 23

Ein Entscheidungsproblem X ist coNP-vollständig,

Answer 23

wenn X ∈ coNP und alle Y ∈ coNP polynomiell auf X reduzierbar sind

Question 24

coNP-vollständige Probleme sind ….

Answer 24

Non-Ham-Cycle, UNSAT und TAUTOLOGY

Question 25

Zwei Graphen G1 = (V1, E1) und G2 = (V2, E2) sind isomorph, wenn ..

Answer 25

es eine Bijektion f : V1 → V2 gibt,

die Adjazenz und Nicht-Adjazenz erhält.

Question 26

GRAPH-ISOMORPHUS liegt in

Answer 26

NP.

Question 27

GRAPH-ISOMORPHUS auf Graphen mit n Knoten

kann in Zeit gelöst werden (wobei p ein Polynom ist)

Answer 27

2^p(log n)

Question 28

Exponential Time Hypothesis (ETH)

Answer 28

Es existiert eine reelle Zahl δ > 0,

sodass kein Algorithmus 3-SAT in Zeit O(2^δn) löst.

Question 29

Definition

Ein Entscheidungsproblem X ⊆ Σ* heisst NP intermediate, wenn…

Answer 29

L ∈ NP und wenn sowohl L ∉ P als auch L ∉ NPC gilt.

Question 30

Komplexitätsklasse (N)PSPACE

Answer 30

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.

Question 31

Satz von Savitch

Answer 31

PSPACE = NPSPACE

Question 32

Problem: QUANTIFIED-SAT (Q-SAT) liegt in PSPACE

Answer 32

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 ϕ

Question 33

Definition: Komplexitätsklasse EXPTIME

Answer 33

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.

Question 34

Das k-Schritt-HALTEPROBLEM liegt in EXPTIME.

Answer 34

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?

Question 35

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Answer 35

Satz