Ψ Die Informatikseite

Menü
Unterabschnitte

Platzkomplexität

PSPACE

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 Backtrackingalgorithmus25 die NTM für SAT simulieren. Die Simulation belegt nur polynomiellen Platz, nämlich soviel Platz wie die Länge der Formel26: $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 $U$, die mitzählt, wieviel Bandzellen $\tau$ benutzt:
  • Wenn die Turingmaschine $\tau$ akzeptiert, akzeptiert die Turingmaschine $U$ 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 $NP$). 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 $PSPACE$ ist im Platz durch ein Polynom $p(\vert x\vert)$ beschränkt. Er ergibt sich für die Gesamtanzahl der Konfigurationen27 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 $c$ 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: $PSPACE=NPSPACE$

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

√úbersicht



Fußnoten

... Backtrackingalgorithmus25
Tiefensuche
... Formel26
sorry, doch keine Fussnote.
... Konfigurationen27
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.