Platzkomplexität ::: Theoretische Informatik

Eine Sprache $L\subseteq\Sigma^{*}$ ist genau dann $\in PSPACE$ , wenn gilt:

$\begin{displaymath}S_{\tau}(n)=O(poly(n))\end{displaymath}$

SAT $\in$ PSPACE

Man kann mit Hilfe eines Backtrackingalgorithmus²⁵ die NTM für SAT simulieren. Die Simulation belegt nur polynomiellen Platz, nämlich soviel Platz wie die Länge der Formel²⁶: $O(\vert\alpha\vert)$ . (Dieser Beweis ist ähnlich dem von $NP\subseteq PSPACE$ )

In-Place Acceptance $\in$ PSPACE

In-Place-Acceptance bedeutet, daß die Turingmaschine $\tau$

in $s_{\tau}(x)\leq \vert x\vert$ Platz
akzeptiert oder verwirft.

Wir benutzen eine universelle Turingmaschine

, die mitzählt, wieviel Bandzellen $\tau$ benutzt:

Wenn die Turingmaschine $\tau$ akzeptiert, akzeptiert die Turingmaschine auch.
Kommt sie über die erlaubte Anzahl $\vert x\vert$ , der Länge des Eingabewortes, so verwirft sie.
Kommt eine Konfiguration doppelt vor (daran kann man erkennen, daß sie Turingmaschine endlos laufen wird), so verwirft sie.
Es liegt nun nahe, daß wir die alten Konfigurationen in der Turingmaschine einfach speichern. Dies würde allerdings zuviel Platz kosten. Statt dessen speichern wir die aktuelle Konfiguration und simulieren die gesamte Turingmaschiene $\tau$ noch einmal von Anfang an, generieren dabei alle alten Konfigurationen und vergleichen.

NP $\subseteq$ PSPACE

Wir benutzen eine Tiefensuche, um den Berechnungsbaum von der Turingmaschine, welche in NP liegt zu durchgehen.
Die Rekursionstiefe ist durch ein Polynom $p(\vert x\vert)$ beschränkt (Definition von

). Bei einem PTIME-Algorithmus darf der Berechnungsbaum höchstens polynomielle Tiefe haben, um die Rekursion zu speichern. Das ist hier erfüllt.

PSPACE $\subseteq$ EXPTIME

Die Turingmaschine in

ist im Platz durch ein Polynom $p(\vert x\vert)$ beschränkt. Er ergibt sich für die Gesamtanzahl der Konfigurationen²⁷ der Turingmaschine:

$\begin{displaymath}\begin {array}{ccccc}\underbrace{p(\vert x\vert)}&\cdot&\unde... ...o}gl.\,Zust\uml {a}nde&&m\uml {o}gl.\,Bandinhalte\\ \end{array}\end{displaymath}$

Wir können eine Konstante

finden, so dass gilt:

$\begin{displaymath}c^{q(\vert x\vert)}>p(\vert x\vert)\cdot\vert Q\vert\cdot\vert\Gamma\vert^{p(\vert x\vert)}\end{displaymath}$

$\Rightarrow$ exponentiell beschränkt

Satz von Savitch:

Haben wir keinen Beweis (glücklicherweise) gemacht
Wir haben nur gesagt, daß nach diesem Satz gilt:

$\begin{displaymath}PSPACE=NPSPACE\end{displaymath}$

Übersicht über die Komplexitätsklassen

Fußnoten

... Backtrackingalgorithmus ²⁵: Tiefensuche
... Formel ²⁶: sorry, doch keine Fussnote.
... Konfigurationen ²⁷: Also Möglichkeiten, wie die Zeichen auf dem Band stehen können, Möglichkeiten wie der Zeiger stehen kann und Möglichkeiten in welchem Zustand sich die Turingmaschine momentan befindet.

Zeitkomplexität Komplexitätsklassen NPC Beweise