Informatik

Was besagt der Satz von Savitch?

Für $s(n)\ge\log n$ gilt:

$$\operatorname{NSPACE}(s(n))\subseteq \operatorname{DSPACE}(s(n)^2).$$

Nichtdeterministischer Speicher lässt sich also mit quadratisch mehr deterministischem Speicher simulieren.