Satz von Savitch

Satz (Savitch): NPSPACE(f) $\subseteq$ DPSPACE(f²).

(N: nichtdeterministisch, D: deterministisch)

Beweis: für M $\in$ NPSPACE konstruiere Formel F wie vorhin (Größe?)

dann teste F $\in$ QBF-SAT mit einer DPSPACE-Maschine.