Satz PSPACE echte Teilmenge von EXPSPACE
Einfache Sprache
Def. Satz PSPACE ist eine echte Teilmenge von EXPSPACE
PSPACE ist eine echte Teilmenge von EXPSPACE. Also
$$\mathbf{PSPACE}\subset\mathbf{EXPTIME}\;.$$
Beweis: Unter Zuhilfenahme des Raumhierarchiesatz ergibt sich folgende Gleichung:
$$\begin{align}\mathbf{PSPACE} &= \bigcup_k\mathbf{SPACE}(n^k)&\Huge|\normalsize\text{Def. $\mathbf{PSPACE}$}\\&\subseteq \mathbf{SPACE}(n^{\log n})&\Huge|\normalsize\text{?}\\&\subset \mathbf{SPACE}(2^n)&\Huge|\normalsize\text{Raumhierarchiesatz}\\&\subseteq \bigcup_k\mathbf{SPACE}(2^{n^k})&\Huge|\normalsize\text{?}\\&= \mathbf{EXPSPACE}&\Huge|\normalsize\text{Def. $\mathbf{EXPSPACE}$}\\\end{align}$$Home: