Einführung Komplexität Flashcards
Nichtdeterministische Turing-Maschine
k kann von Startkonfiguration erreicht werden (Berechnungspfad)
Zertifikat - Definition
M berechnete Funktion
Mächtigkeit von DTM und NTM - Theorem
Für jede NTM N gibt es eine DTM M mit T(M) = T(N)
Was ist die Zentrale Frage der algorithmischen Komplexität
Wann ist ein Algorithmus effizient bzw. ein Berechnungsproblem effizient lösbar?
0-Notation zur Laufzeitanalyse - Definition
Was will man mit der 0-Notation erreichen
Effizienz von Algorithmen unabhängig von Rechnetechnik & Programmiersprache bestimmen.
time_M - Definition
DTIME(f(n)) - Definition
P - Definition
“deterministisch, in Plynomzeit”
time_N - Definition
NTIME(f(n)) - Definition
NP - Definition
In welchem Mengenverhältnis stehen P und NP
P ist eine Teilmenge von NP
Alternative Definition für NP (“Guess and Check”)
Ist P = NP?
Man weis es nicht, geht aber davon aus, das P eine echte Teilmenge von NP ist.
3(2)-Coloring - Problem
Wie schwierig ist das 3(2)-Coloring Problem?
Beide Probleme liegen in NP und 2-Coloring sogar in P
Shortest Path (Longest Path) - Problem
3-SAT (2-SAT) - Problem
Wie schwierig ist das Shortest Path (Longest Path) Problem?
Beide Probleme liegen in NP und Shortest Path liegt sogar in P (Breitensuche).
Wie schwierig ist das 3-SAT (2-SAT) Problem ?
Beide Probleme liegen in NP und 2-SAT liegt sogar in P.
