Satz NL ist eine echte Teilmenge von PSPACE
Einfache Sprache
Def. Satz NL ist eine echte Teilmenge von PSPACE
NL ist eine echte Teilmenge von PSPACE.
Beweis: Wir nutzen den Satz von Savitch und den Raumhierarchiesatz in folgender Gleichung:
$$\begin{align}\mathbf{NL} &\subseteq \mathbf{SPACE}(\log^2n) &\Huge|\normalsize\text{Satz von Savitch}\\&\subset \mathbf{SPACE}(n) &\Huge|\normalsize\text{Raumhierarchiesatz}\\\end{align}$$