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.

Aussage[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

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

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

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

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

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

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

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

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

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext 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.