Satz PSPACE Teilmenge von EXPTIME

Einfache Sprache

Def. Satz PSPACE Teilmenge von EXPTIME

Es gibt

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

Beweis: Sei $f(n)\leq n$. Eine TM die mit einer Platzkomplexität von $f(n)$ kann höchstens $f(n)2^{O(f(n))}$ unterschiedliche Konfigurationen haben. Das folgt aus einer Generalisierung des Satz Anzahl der Konfigurationen eines LBTM. Eine TM die hält “muss” keine Konfiguration wiederholen, in dem Sinn das wenn sich eine Konfiguration wiederholt, die Konfigurationen dazwischen einen Schleife bilden die man auslassen kann. Also hat eine TM mit Platzkomplexität $f(n)$ eine Zeitkomplexität von $f(n)2^{O(f(n))}$. Daraus folgt $\mathbf{PSPACE}\subseteq\mathbf{EXPTIME}\;.$