Satz von Savitch

Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares Problem auf einer deterministischen Turingmaschine mit einer quadratisch höheren Platzschranke gelöst werden kann.

Eine Folgerung aus dem Satz von Savitch ist die Gleichheit von PSPACE und NPSPACE.

Formale Definition

Sei $s:\mathbb{N}\rightarrow\mathbb{N}$ eine bandkonstruierbare Funktion mit $s(n)\geq\log(n)$. Dann gilt:

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

Literatur

• Walter Savitch: Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.