Zeitkomplexität ::: Theoretische Informatik

Guess and Check-Methode
Bei der Guess and Check-Methode wird eine Kombination mit Hilfe des ,,Orakels'' einfach geraten. Dabei wird so geraten, daß direkt das richtige Ergebnis geraten wird. Gibt es kein richtiges Ergebnis, so wird ein falsches Ergebnis ausgegeben. Das von dem nichtdeterministischen Guess-Bereich erratene Ergebnis wird im deterministischen Check-Bereich noch einmal auf Richtigkeit überprüft. Hier stellt sich heraus, ob es wirklich richtig ist oder ob die Guess-Methode ein falsches Ergebnis zurückgegeben hat, weil es kein richtiges gibt.
SAT
$\alpha$ : Die zu überprüfende Formel, wobei z.B. $\alpha\in\{0,1,\wedge,\neg,(,)\}$
Wir raten zunächst mit Hilfe des ,,Orakels'' eine Belegung der Formel. Ist das SAT-Problem erfüllbar, bekommen wir eine erfüllbare Belegung zurück. Wenn nicht irgendeine Belegung.
Dann können wir in

Schritten überprüfen, ob die geratene Belegung tatsächlich eine wahre Belegung ist.
Wir benötigen polynomielle Laufzeit für beide Teilalgorithmen, da die Anzahl der Literale durch $\vert\alpha\vert$ beschränkt ist.

$\begin{displaymath}O(poly(\vert\alpha\vert)\end{displaymath}$

Primzahlen

Unter dem deterministischen. logarithmischen Kostenmaß hat der Primzahltest die Laufzeit $\Theta(n\log{n})$ , unter dem nichtdeterministischen Kostenmaß die Laufzeit

.
Dies kommt dadurch zustande, daß wir mit Guess-Methode einen möglichen Teiler raten. Es wird ein Teiler der zu testenden Zahl geraten, wenn es einen gibt. Andernfalls wird irgendeine Zahl geraten. Nachdem wir den möglichen Teiler geraten haben, können wir testen, ob dieser geratene Teile wirklich Teiler der zu testenden Zahl ist.

Cliquenproblem

Kodierung des Graphen
Man kann den Graph G folgendermaßen codieren:

$\begin{displaymath}code(G)=\char93 \char93 bin(n)\char93 \char93 bin(von)\char93 bin(nach)\char93 \char93 \end{displaymath}$

Kodierung des CP
Man kann das gesamte CP folgendermaßen kodieren:

$\begin{displaymath}code(G)\char93 \char93 \char93 bin(k)\end{displaymath}$

Eingabegröße des CP
Die Eingabegröße ist also

$\begin{displaymath}\begin {array}{cccccc}\underbrace{\vert code(G)\vert}&+&\unde... ...&\char93 &&bin(k)&nur\,der\,Graph\,ist\,relevant\\ \end{array}\end{displaymath}$

Laufzeit des CP
Für ein deterministisches Verfahren können wir für die untere Schranke die Laufzeit mit

$\begin{displaymath}\Omega\left(n\choose k \right)\end{displaymath}$

festlegen. Dies beruht auf der Tatsache, daß wir $n\choose k$ Möglichkeiten haben, eine k-er Clique aus allen Knoten auszuwählen²³. Wir testen jede Clique in konstanter Zeit.
Es gilt die Abschätzung:

$\begin{displaymath}\Omega\left(n\choose k \right)\geq 2^{\frac{n}{2}}=\sqrt{2}^{n}\end{displaymath}$

$\Rightarrow$ exponentielle Laufzeit²⁴

Zeitkomplexitätsklassen

Es gibt folgende Klassen im deterministischen und im nichtdeterministischen:

DTIME	NTIME
DSPACE	NSPACE

P,NP,EXPTIME

$P=PTIME=\bigcup_{k\geq 1}(n^{k})$

$NP=NPTIME=\bigcup_{k\geq 1}(n^{k})$

$EXPTIME=\bigcup_{c\geq 1}\bigcup_{k\geq 1}(c^{n^{k}})$

NP $\subseteq$ EXPTIME

NP liegt in EXPTIME
Dies können wir beweisen, indem wir die NTM $\tau'$ , die den NP-Algorithmus ausführt mit einer deterministischen DTM $\tau$ in EXPTIME simulieren.
Es liegt ein Berechnungsbaum vor, welchen wir mit Hilfe einer Breitensuche oder einem Preorderdurchlauf durchgehen. Da die nichtdeterministische Turingmaschine $\tau'$ polynomiell beschränkt ist, ist die maximale Tiefe des Baumes polynomiell beschränkt.

Der Verzweigungsgrad jedes Knotens dieses Baumes ist

$\begin{displaymath}c=\vert\delta(q,a)\vert\leq\vert\{L,N,R\}\vert\cdot\vert\Sigma\vert\cdot\vert Q\vert\end{displaymath}$

somit gilt für die Knotenanzahl

$\begin{displaymath}O(c^{p(\vert x\vert)})\end{displaymath}$

Also ist die Simulation von $\tau'$ exponentiell beschränkt
$\Rightarrow$ NP $\subseteq$ EXPTIME

Polynomialzeit akzeptierende NTMs

Auf wenn nur Wörter $w\in L$ von der Turingmaschine $\tau$ in $O(p(\vert x\vert))$ akzeptiert werden, können wir die gesamte Turingmaschine beschränken, indem wir alle irgendwann verwerfenden oder endlosen Berechnungen abschneiden, wenn sie über polynomielle Laufzeit hinaus laufen.

Fußnoten

... auszuwählen ²³: Kombinatorik
... Laufzeit ²⁴: Das Nichtdeterministische Verfahren für das CP hat polynomielle Laufzeit.

Unterschiedliche Problemvarianten Komplexitätsklassen Platzkomplexität

Ψ Die Informatikseite