Satz von Savitch

Der Satz v​on Savitch o​der Theorem v​on Savitch i​st ein Satz a​us der Komplexitätstheorie, d​er 1970 v​on Walter Savitch bewiesen wurde. Er besagt, d​ass ein v​on einer nichtdeterministischen Turingmaschine m​it einer bestimmten Platzkomplexität lösbares Problem a​uf einer deterministischen Turingmaschine m​it einer quadratisch höheren Platzschranke gelöst werden kann.

Eine Folgerung a​us dem Satz v​on Savitch i​st die Gleichheit v​on PSPACE u​nd NPSPACE.

Aussage

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

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

Beweisidee

Nehmen wir an, ${\displaystyle L\in {\mbox{NSPACE}}(s(n))}$, d. h., es gibt eine nichtdeterministische Turingmaschine ${\displaystyle M}$ mit Platzbedarf ${\displaystyle s(n)}$, welche genau die Sprache ${\displaystyle L}$ akzeptiert. Aufgrund der Platzbeschränkung kann ${\displaystyle M}$ nur ${\displaystyle |Q|\cdot n\cdot s(n)\cdot |\Gamma |^{s(n)}}$ verschiedene Konfigurationen annehmen, wobei ${\displaystyle |Q|}$ die Anzahl ihrer Zustände und ${\displaystyle |\Gamma |}$ die Anzahl verschiedener Bandsymbole bezeichne. Wenn diese Maschine also eine Eingabe ${\displaystyle w}$ der Länge ${\displaystyle n}$ akzeptiert, (genau dann) gibt es auch einen akzeptierenden Lauf mit weniger als ${\displaystyle |Q|\cdot n\cdot s(n)\cdot |\Gamma |^{s(n)}}$ Rechenschritten. Betrachten wir ein Prädikat

${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,i){\stackrel {\text{def}}{\iff }}}$ Die NTM ${\displaystyle M}$ kann ausgehend von der Konfiguration ${\displaystyle \alpha }$ innerhalb von ${\displaystyle 2^{i}}$ Rechenschritten die Konfiguration ${\displaystyle \beta }$ erreichen.

Bezeichne ${\displaystyle {\mbox{Start}}(w)}$ die Anfangskonfiguration der NTM bei Eingabe des Wortes ${\displaystyle w}$ und ${\displaystyle {\mbox{Accept}}}$ die akzeptierende Haltekonfiguration. Dann können wir „${\displaystyle M}$ akzeptiert ${\displaystyle L}$“ (mit geeigneter Konstante ${\displaystyle C}$ abhängig von ${\displaystyle s}$ und ${\displaystyle M}$) formulieren als:

${\displaystyle {\mbox{Reach}}({\mbox{Start}}(w),{\mbox{Accept}},C\cdot s(n))\iff w\in L}$.

Wir wissen, dass eine deterministische Turingmaschine mit Platzbedarf ${\displaystyle s(n)}$ berechnen kann, ob ${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,1)}$ zutrifft. Außerdem hat ${\displaystyle {\mbox{Reach}}}$ die Eigenschaft

${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,i+1)\iff }$ es gibt eine Zwischen-Konfiguration ${\displaystyle \gamma }$ mit ${\displaystyle {\mbox{Reach}}(\alpha ,\gamma ,i)}$ und ${\displaystyle {\mbox{Reach}}(\gamma ,\beta ,i)}$.

Eine deterministische Turingmaschine kann ${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,i+1)}$ berechnen, indem sie alle möglichen Konfigurationen ${\displaystyle \gamma }$ aufzählt und für jedes ${\displaystyle \gamma }$ jeweils (nacheinander) ${\displaystyle {\mbox{Reach}}(\alpha ,\gamma ,i)}$ und ${\displaystyle {\mbox{Reach}}(\gamma ,\beta ,i)}$ berechnet. Dazu genügen (für geeignetes ${\displaystyle C'}$) ${\displaystyle C'\cdot s(n)}$ Bandzellen für ${\displaystyle \gamma }$ und ${\displaystyle C'\cdot i\cdot s(n)}$ Bandzellen für die Berechnung von ${\displaystyle {\mbox{Reach}}(\alpha ,\gamma ,i)}$ bzw. ${\displaystyle {\mbox{Reach}}(\gamma ,\beta ,i)}$. Insbesondere kann eine solche DTM also mit Platzbedarf ${\displaystyle C\cdot C'\cdot s^{2}(n)}$ ermitteln, ob ${\displaystyle {\mbox{Reach}}({\mbox{Start}}(w),{\mbox{Accept}},C\cdot s(n))}$ und damit, ob ${\displaystyle w\in L}$.

Die Wahl geeigneter Konstanten ${\displaystyle C,C'}$ ist insbesondere wegen ${\displaystyle s(n)\in \Omega (\log n)}$ möglich.

Siehe auch

• Liste von Sätzen der Informatik

Literatur

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