VL-12: P und NP

Question 1

Was ist die Worst-Case Laufzeit?

Answer 1

Die Worst-Case Laufzeit tA(n) eines Algorithmus A misst die maximale Laufzeit von A mit Eingabe n im logarithmischen Kostenmaß einer RAM

Question 2

Was bedeutet es, wenn ein Algorithmus polynomiell beschränkt ist?

Answer 2

Es gibt ein ɑ so das tA(n) ∈ O(n^ɑ)

Question 3

Was ist Komplexitätsklasse P?

Answer 3

P ist die Klasse aller Entscheidungsprobleme, für die es einen polynomiellen Algorithmus auf einer TM gibt.

Question 4

Was ist eine nicht-deterministische TM?

Answer 4

TM mit Übergangsrelation anstatt Funktion. Also mehrere Zustandsübergänge möglich

Question 5

Was ist die Komplexitätsklasse NP?

Answer 5

NP ist die Klasse der Entscheidungsprobleme, die von einer NTM in polynomieller Zeit gelöst werden können.

Question 6

Wie stellt man fest ob ein Problem in NP liegt?

Answer 6

Zertifikat - Verifizierer:
- L in NP ↔ Es existiert ein deterministischer Algorithmus V (Verifizierer) und ein polynom p, für die gelten:
x in L ↔ ∃ y in {0,1}* (Zertifikat), y ≤ p(|x|): V akzeptiert y#x