P versus NP

Question 1

Definition: Worst Case Laufzeit t_A(n) eines Algorithmus A

Answer 1

maximale Laufzeitkosten auf Eingaben der Länge n bezüglich des logarithmisches Kostenmaßes der RAM.

Question 2

Worst Case Laufzeit t_A(n) eines Algorithmus A ist polynomiell beschränkt, falls gilt

Answer 2

∃α ϵ N : t_A(n) ϵ O(n^α)

Question 3

Ein Algorithmus mit polynomiell beschränkter Worst Case Laufzeit heißt

Answer 3

Polynomialzeitalgorithmus

Question 4

SORTIEREN kann in …. Zeit gelöst werden.

Answer 4

polynomieller

Question 5

Problem SORTIEREN

Answer 5

Eingabe: Zahlen a_1, …, a_n ϵ N in Binärdarstellung
Ausgabe: Die aufsteigend sortierte Folge der Eingabezahlen

Question 6

Beispiele von Probleme mit polynomiellen Algorithmus lösbar

Answer 6

Eulerkreis
Kürzester Weg 
Minimaler Spannbaum
Maximaler Fluss
Maximum Matching
Primzahltest
Grösste gemeinsamer Teiler

Question 7

Definition: Komplexitätsklasse P

Answer 7

Die Klasse aller Entscheidungsprobleme, für die es einen polynomiellen Algorithmus gibt

Question 8

Problem GRAPHZUSAMMENHANG

Answer 8

Eingabe: Ein ungerichteter Graph G=(V, E)
Ausgabe: Ist G zusammenhängend?

Question 9

GRAPHZUSAMMENHANG ϵ … (Welche Komplexitätsklasse?)

Answer 9

P

Question 10

Definition: Non-deterministische Turingmaschine (NTM)

Answer 10

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} )

Question 11

Der Unterschied zwischen TM und NTM:

Answer 11

Zustandsüberführung ist durch eine Relation und nicht durch eine Funktion gesteuert:
δ ⊆ ( (Q\ {notq} ⋅ Γ) ⋅ ( Q ⋅ Γ ⋅ {L,R,N} )

Question 12

Rechenweg einer NTM =

Answer 12

Konfigurationsfolge, die mit Startkonfiguration beginnt und mit Nachfolgekonfiguration fortgesetzt wird, bis eine Endkonfiguration im Zustand not q erreicht wird.

Question 13

maximale Verzweigungsgrad des Berechenbaumes ist Δ :=

Answer 13

max{ |δ(q,a)| | q ϵ Q\ {notq}, a ϵ Γ }

Question 14

Eine NTM M akzeptiert die Eingabe x ϵ Σ*, falls…

Answer 14

es mindestens eine Rechenweg von M gibt, der in eine Konfiguration mit akzeptierendem Zustand führt.

Question 15

Die Laufzeit einer NTM M auf einer Eingabe x:

1. Falls x ϵ L(M), so ist die Laufzeit T_M(x) =…
2. Falls x ∉ L(M), so ist die Laufzeit T_M(x) =….

Answer 15

1. die Länge der kürzesten akzeptierenden Rechenwegs von M auf x
2. 0

Question 16

Definition: Komplexitätsklasse NP

Answer 16

Die Klasse aller Entscheidungsprobleme, die durch eine NTM M erkannt werden, deren Worst Case Laufzeit t_M(n) polynomiell beschränkt ist.

Question 17

Problem CLIQUE

Answer 17

Eingabe: Ein ungerichteter Graph G=(V,E); eine Zahl k
Frage: Enthält G eine Clique mit ≥ k Knoten?

Question 18

CLIQUE ϵ …. (welche Komplexitätsklasse)

Answer 18

NP

Question 19

Zertifikat Charakterisierung von NP

Answer 19

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

Question 20

Problem: Satisfiability (SAT)

Answer 20

Eingabe: Eine Boole’sche Formel φ in KNF über einer
Boole’schen Variablenmenge X = {x1, . . . , xn}
Frage: Existiert eine Wahrheitsbelegung von X, die φ erfüllt?

Question 21

SAT ϵ … (Welche Komplexitätsklasse?)

Answer 21

NP

Question 22

Problem: Independent Set (INDEP-SET)

Answer 22

Eingabe: Ein ungerichteter Graph G = (V, E); eine Zahl k
Frage: Enthält G eine unabhängige Menge mit ≥ k Knoten?

Question 23

INDEP-SET ϵ … (Welche Komplexitätsklasse?)

Answer 23

NP

Question 24

Problem: Vertex Cover (VC)

Answer 24

Eingabe: Ein ungerichteter Graph G = (V, E); eine Zahl k
Frage: Enthält G ein Vertex Cover mit ≤ k Knoten?

Question 25

VC ϵ … (Welche Komplexitätsklasse?)

Answer 25

NP

Question 26

Problem: Hamiltonkreis (Ham-Cycle)

Answer 26

Eingabe: Ein ungerichteter Graph G = (V, E)
Frage: Besitzt G einen Hamiltonkreis?

Question 27

Problem: Travelling Salesman Problem (TSP)

Answer 27

Eingabe: Städte 1, . . . , n; Distanzen d(i, j); eine Zahl γ
Frage: Gibt es eine Rundreise (TSP-Tour) mit Länge höchstens γ?

Question 28

Problem: Exact Cover (EX-COVER)

Answer 28

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?

Question 29

Problem: SUBSET-SUM

Answer 29

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?

Question 30

Problem: PARTITION

Answer 30

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?