Satz P Teilmenge von PSPACE

Einfache Sprache

Def. Satz P Teilmenge von PSPACE

Es gilt

$$\mathbf{P}\subseteq\mathbf{PSPACE}\;.$$

Idee: Eine TM die nicht lange Läuft, also eine kleine Zeitkomplexität hat, kann auch nicht viel Band “verbrauchen” (in dem Sinn das der Lese-Schreibkopf nicht so weit nach Rechts kommt).

Beweis: Sei $f(n)\leq n$. Eine TM die mit einer Zeitkomplexität $f(n)$ kann höchstens $f(n)$ Platzkomplexität haben, da die Maschine höchstens eine neue Band-Zelle pro Schritt der Berechnung entdecken.