Satz von Savitch

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Sei s:\mathbb{N}\rightarrow\mathbb{N} eine platzkonstruierbare Funktion mit s(n)\in \Omega(\log(n)). Dann gilt:

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

Beweisidee[Bearbeiten]

Der Beweis läuft über eine s-platzbeschränkte nichtdeterministische Turingmaschine M. \alpha, \beta, ... seien Konfigurationen der Turingmaschine M . Mit Hilfe des Prädikates Reach(\alpha, \beta, i) kann gezeigt werden, dass für eine Eingabe w \in \Sigma^* die Konfiguration \alpha in höchstens 2^i Schritten in \beta überführt werden kann. Start(w) sei die Startkonfiguration von w und Accept die akzeptierende Konfiguration. Aus der Konstruktion von M lässt sich eine explizite Konstante c gewinnen, so dass gilt:

w \in L \iff Reach(Start(w), Accept, c \cdot s(|w|))

Dies lässt sich für i = 0 direkt berechnen und für i > 0 mit folgendem Schema:

Reach(\alpha, \beta, i) \iff \exists \text{ Konfiguration }\gamma \text{ mit } |\gamma| \leq s(|w|): Reach(\alpha, \gamma, i-1) \text{ und } Reach(\gamma, \beta, i-1)

Das kann in ein deterministisches Programm übersetzt werden und der maximale Platzbedarf durch c' \cdot s(|w|) \cdot (i+1) zu \mathcal{O}(s^2) abgeschätzt werden. Dies gewinnen wir aus einer Induktion nach i mit einer gewissen Konstanten c'.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  •  Walter Savitch: Relationships between nondeterministic and deterministic tape complexities. In: Journal of Computer and System Sciences. Bd. 4, Nr. 2, Elsevier, San Diego 1970, ISSN 0022-0000, S. 177–192, doi:10.1016/S0022-0000(70)80006-X.