Satz von Savitch

Einfache Sprache

Def. Satz von Savitch

Für eine beliebige Funktion $f:\mathbb N\to\mathbb R^+$ mit $f(n)\geq n$ gilt

$$\mathbf{NSPACE}(f(n))\subseteq\mathbf{SPACE}(f^2(n))\;.$$

Idee: Wir müssen eine NDTM mit einer Platzkomplexität von $f(n)$ deterministisch simulieren. Dazu zuerst warum der naive Ansatz nicht funktioniert.

Der naive Ansatz wäre es alle möglichen Kombinationen der nichtdeterministischen Entscheidungen auszuprobieren. Dazu muss aber gespeichert werden welche Kombination gerade getestet wird. Eine Kombination die $f(n)$ Platz benutzt kann eine Laufzeit von bis zu $2^{O(f(n))}$ haben. Jeder dieser Schritte könnte nichtdeterministisch sein. Um eine mögliche Berechnung zu testen müssten also bis zu $2^{O(f(n))}$ nichtdeterministische Entscheidungen gespeichert werden. Das bedeutet wir benötigen $2^{O(f(n))}$ Platzkomplexität, was größer als unser Ziel von $O(f^2(n))$ ist.

Unser Ansatz betrachtet zunächst ein generellere Problem: Gegeben sind zwei Konfigurationen der NDTM $c_1$ und $c_2$ und eine Zahl $t$. Teste ob man von $c_1$ zu $c_2$ in $t$ Schritten mit nur $f(n)$ Platz kommen kann. Das Problem wird auch yieldability problem genannt. Wir können das yieldability problem benutzten in dem $c_1$ die Startkonfiguration, $c_2$ die akzeptierende Konfiguration und $t$ gleich $f(n)$ ist.

Für yieldability problem geben wir einen deterministischen, rekursiven Algorithmus an. Er sucht eine Zwischenkonfiguration $c_m$ und testet rekursiv ob c_m von $c_1$ aus in $t/2$ Schritten erreichbar ist und ob $c_2$ von $c_m$ aus in $t/2$ Schritten erreichbar ist. Dadurch können wir den Platz für die zwei rekursiven Tests wiederverwenden was signifikant Platz spart.

Der Algorithmus hat einen Rekursions-Stapel (Stapelspeicher). Bei jeder Stufe benötigt $O(f(n))$ Speicher um eine Konfiguration zu speichern. Die Tiefe des Stapels ist $\log t$, wobei $t$ die maximale Laufzeit der NDTM ist. Wir haben also $t=2^{O(f(n))}$ so, dass $\log t = O(f(n))$. Daher benötigt die deterministische Simulation nur $O(f^2(n))$ Platz.

Beweis: Sei $N$ eine NDTM, die die Sprache $A$ in Platzkomplexität $f(n)$ entscheidet. Wir konstruieren eine DTM $M$ die $A$ entscheidet. $M$ benutzt die Prozedur $\mathrm{CANYIELD}$, die das yieldability problem löst.

Sei $w$ eine Eingabe von $N$. Für zwei Konfigurationen $c_1$ und $c_2$ von $N$, und einer natürlichen Zahlen $t$, akzeptiert $\mathrm{CANYIELD}(c_1,c_2,t)$ wenn $N$ von $c_1$ nach $c_2$ gehen kann in $t$ oder weniger Schritten. Sonst verwirft $N$. O.b.d.A nehmen wir an das $t$ eine Zweierpotenz ist. $\mathrm{CANYIELD}$ arbeitet wie folgt:

1. Falls $t=1$ überprüfe ob $c_1=c_2$ und ob $c_2$ eine mögliche Folgekonfiguration von $c_1$ (bzgl. $N$) ist. Falls beides Falsch ist, dann verwerfe, sonst akzeptiere.
2. Falls $t> 1$, dann machen für jede mögliche Konfiguration $c_m$:
   1. Führe $\mathrm{CANYIELD}(c_1,c_m,t/2)$ aus.
   2. Führe $\mathrm{CANYIELD}(c_m,c_2,t/2)$ aus.
   3. Falls beide Schritte davor akzeptiert haben, dann akzeptiere
3. verwerfe

Jetzt definieren wir $M$. Dafür passen wir $N$ so an, dass wenn $N$ akzeptiert, das Band aufräumt (alles mit Platzhaltern überschreibt), den Lese-Schreibkopf nach ganz links bewegt. Diese Konfiguration nennen wir $c_\mathrm{accept}$. Sei $c_\mathrm{start}$ die Startkonfiguration von $N$ mit der Eingabe $w$. Wir wählen eine Konstante $d$ so, dass $N$ nicht mehr als $2^{df(n)}$ Konfigurationen hat. Dann wissen wir das $2^{df(n)}$ eine obere Schranke für die Laufzeit von $N$ mit der Eingabe $w$ ist. Bemerke das $n=|w|$. $M$ arbeitet wir folgt:

1. Gebe das Ergebnis von $\mathrm{CANYIELD}(c_\mathrm{start},c_\mathrm{accept}, 2^{df(n)})$ aus.

$\mathrm{CANYIELD}$ löst offensichtlich das yieldability problem. Also wird $N$ korrekt von $M$ simuliert. Nun muss noch gezeigt werden dann $M$ die Platzkomplexität $O(f^2(n))$ hat.

Immer wenn $\mathrm{CANYIELD}$ sich selbst rekursiv aufruft speichert es die aktuelle Rekursionstiefe und Werte $c_1$,$c_2$ und $t$ auf dem Stapel. Für jeden Rekursionsschritt wird also $O(f(n))$ Platz benötigt. Überdies wird in jedem Rekursionsschritt die $t$ halbiert. Da zu beginn $t=2^{df(n)}$ ergibt sich eine Rekursionstiefe von $O(\log 2^{df(n)}) = O(f(n))$. Also ist der Gesamte Platzbedarf $O(f^2(n))$ wie behauptet.

Ein Problem dieses Beweises ist, dass $M$ die Laufzeit $f(n)$ von $N$ wissen muss bevor sie $\mathrm{CANYIELD}$ aufruft. Wir können das vermeiden indem $M$ modifizieren. Die neue DTM $M'$ versucht inkrementell für $f(n)$ immer größere Laufzeiten $1,2,3,\ldots$ aus. Für jeden Wert $f(n)=i$ benutzt $M'$ $\mathrm{CANYIELD}$ um herauszufinden ob eine akzeptierende Konfiguration erreichbar ist. Zusätzlich benutzt $M'$ $\mathrm{CANYIELD}$ um zu überprüfen ob $N$ mind. $i+1$ Platz benutzt. Das erfolgt indem überprüft wird ob in $N$ mindestens eine der Konfiguration der Länge $i+1$ von der Startkonfiguration aus erreichbar ist. Falls nicht verwerfe. Sonst fahre fort mit $f(n) = i+1$.