Kapitel 9.7: Theoretische Informatik 2 - Bachelor-Studium Informatik

9.7 Beschränkter Speicherplatz

In den vergangen Kapiteln haben wir die Laufzeit einer Turingmaschine beschränkt und die Komplexitätsklassen studiert, die sich daraus ergeben, allen voran P und NP. Die neben Zeit wohl wichtigste Resource beim Rechnen ist der Platz. Turingmaschinen erlauben uns auch, präzise über den benötigten Speicherplatz zu sprechen. Der Platz einer Konfiguration $C = uqv \in \Gamma^* \times Q \times \Gamma^*$ ist die Anzahl der belegten Speicherzellen, also beispielsweise $|uv|$. Bei $k$ -Band-Maschinen müssen wir das über alle Bänder aufsummieren. Wir können eine Konfiguration also als Tupel in

\begin{align*} \mathcal{C} : Q \times (\Gamma^* \times \Gamma^*)^k \end{align*}

darstellen. Eine Konfiguration $C = (q, (u_1, v_1), \dots, (u_k, v_k))$ besagt dann beispielsweise, dass auf Band $i$ das Wort $u_iv_i$ steht, wobei der Kopf auf dem ersten Zeichen von $v_i$ steht. Die Größe von $C$ ist dann $|C| := |u_1| + |v_1| + \cdots + |u_k| + |v_k|$. Eine Turingmaschine läuft in Platz $s(n)$, wenn für alle $x \in \Sigma^*$ alle erreichten Konfigurationen höchstens die Größe $s(|x|)$ haben. Diese Definition hat den Nachteil, dass der Platzbedarf immer mindestens $n$ ist: bereits die Startkonfiguration $\qstart x_1 x_2 \dots x_n$ besteht ja aus $n$ Zeichen. Das ist aber irgendwie unfair. Wir wollen nur den Platz zählen, der über das Eingabewort hinausgeht. Wenn wir über Platzbedarf sprechen, dann gehen wir von einer Turingmaschine aus, die

ein Eingabeband hat, auf dem sie nur lesen darf;
beliebig viele Arbeitsbänder, auf denen sie lesen und schreiben darf;
ein Ausgabeband, auf dem sie schreiben darf, aber nur nach rechts laufen darf.

Wenn wir eine Sprache $L \subseteq \Sigma^*$ entscheiden wollen, dann brauchen das Ausgabeband nicht wirklich. Wenn wir eine Funktion $f: \Sigma_1^* \rightarrow \Sigma_2^*$ berechnen wollen, dann sehr wohl.

Eingabe und Ausgabe: wenn Sie ein C-Programm schreiben und auf stdout schreiben, dann entspricht diese Operation in gewisser Weise der Turingmaschine, die auf das Ausgabeband schreibt; sie können ja sich den Output auch nicht irgendwie zurückholen. Das lesen von stdin entspricht allerdings nicht ganz dem Eingabeband der Turingmaschine. Ein bedeutender Unterschied ist, dass die Turingmaschine auf dem Eingabeband zwar nicht schreiben darf, aber dennoch beliebig nach rechts und links gehen darf. Das können Sie auf stdin in der Regel nicht.

Streaming-Modell: wenn wir der Turingmaschine verbieten, auf dem Eingabe-Band nach links zu laufen, wenn sie also jedes Eingabezeichen nur einmal lesen darf, dann erhalten wir das sogenannte Streaming-Modell, das in den letzten Jahren an Popularität gewonnen hat, weil wir es heutzutage in vielen Anwendungen mit Datenmengen zu tun haben, die nicht in den Speicher des Rechners passen und auch nur einmal gelesen werden können (z.B. Sensordaten). Im Kurs Effiziente Algorithmen gibt es ein Kapitel zu Streaming-Algorithmen.

Definition 9.7.1 ($\SPACE(s)$). Sei $M$ eine Turingmaschine mit dezidiertem Eingabeband 1 und Ausgabeband $k$. Die Größe einer Konfiguration ist die Größe der Bandinhalte der Arbeitsbänder. Die Konfiguration $C = (q, (u_1, v_1), \dots, (u_k, v_k))$ hat Größe $|u_2| + |v_2| + \cdots + |u_{k-1}| + |v_{k-1}|$. Sei $s : \N \rightarrow \N$. Die Turingmaschine $M$ läuft in Platz $s$, falls

sie für jedes $x \in \Sigma^*$ terminiert und
jede erreichte Konfiguration höchstens Größe $O(s(|x|))$ hat.

Eine Sprache ist in $\SPACE(s)$, wenn es eine Turingmaschine gibt, die in Platz $s$ läuft und sie entscheidet.

Beobachtung 9.7.2 Wenn $M$ in Platz $s(n)$ läuft, dann hat $M$ Laufzeit $2^{O(s(n))}$.

Beweis Für gegebenes $n$ sei $S \in O(s(n))$ der maximale Platzbedarf der Turingmaschine. Es gibt maximal $T := |Q| \cdot \left(|\Gamma|+1\right)^{kS}$ Konfigurationen (warum?). Da $M$ terminiert, kann die Berechnung nicht mehr $T$ Schritte dauern.A$\square$

Übungsaufgabe 9.7.1 Zeigen Sie, dass wir die Bedingung 1 aus Definition 9.7.1 weglassen können, zumindest wenn $s(n)$ zeitkonstruierbar ist.

Die wichtigsten Platzklassen: L und PSPACE

Wir definieren

\begin{align*} \textnormal{PSPACE} := \bigcup_{k \geq 1} \SPACE(n^k) \end{align*}

also die Menge aller Probleme, die man mit polynomiellem Speicherplatz entscheiden kann, und

\begin{align*} \textnormal{L} := \SPACE(\log n) \ . \end{align*}

die Menge aller Probleme, die man mit logarithmischem Speicherplatz entscheiden kann. Man nennt $L$ auch LogSpace.

Übungsaufgabe 9.7.2 Zeigen Sie, dass ${\rm NP} \subseteq {\rm PSPACE}$ gilt. Fangen Sie zum Beispiel an,3-Colorability $\in$ PSPACE zu zeigen.

Übungsaufgabe 9.7.3 Sei Palindrome die Sprache aller Palindromwörter mit Trennungszeichen in der Mitte, also

\begin{align*} \{ucu^{R} \ | \ u \in \{a,b\}^* \} \ . \end{align*}

Zeigen Sie, dass Palindrome $\in$ L

Übungsaufgabe 9.7.4 Zeigen Sie, dass die Sprache aller wohlgeformten Klammerausdrücke in L ist, also die Sprache über $\{a,b\}$ mit

\begin{align*} S&\rightarrow \epsilon \ | \ aSbS \ . \end{align*}

Übungsaufgabe 9.7.5 Seien $f: \Sigma_1 \rightarrow \Sigma_2$ und $g: \Sigma_2 \rightarrow \Sigma_3$ zwei Funktionen. Zeigen Sie, dass, falls $f$ und $g$ in logarithmischem Platz berechnet werden können, dann auch $g \circ f: \Sigma_1 \rightarrow \Sigma_3$. Hinweis: der "offensichtliche" Ansatz funktioniert nicht. Warum nicht?