Satz von Savitch

mathematischer Satz

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.

Sei   eine platzkonstruierbare Funktion mit  . Dann gilt:

 

Beweisidee

Bearbeiten

Nehmen wir an,  , d. h., es gibt eine nichtdeterministische Turingmaschine   mit Platzbedarf  , welche genau die Sprache   akzeptiert. Aufgrund der Platzbeschränkung kann   nur   verschiedene Konfigurationen annehmen, wobei   die Anzahl ihrer Zustände und   die Anzahl verschiedener Bandsymbole bezeichne. Wenn diese Maschine also eine Eingabe   der Länge   akzeptiert, (genau dann) gibt es auch einen akzeptierenden Lauf mit weniger als   Rechenschritten. Betrachten wir ein Prädikat

  Die NTM   kann ausgehend von der Konfiguration   innerhalb von   Rechenschritten die Konfiguration   erreichen.

Bezeichne   die Anfangskonfiguration der NTM bei Eingabe des Wortes   und   die akzeptierende Haltekonfiguration. Dann können wir „  akzeptiert  “ (mit geeigneter Konstante   abhängig von   und  ) formulieren als:

 .

Wir wissen, dass eine deterministische Turingmaschine mit Platzbedarf   berechnen kann, ob   zutrifft. Außerdem hat   die Eigenschaft

  es gibt eine Zwischen-Konfiguration   mit   und  .

Eine deterministische Turingmaschine kann   berechnen, indem sie alle möglichen Konfigurationen   aufzählt und für jedes   jeweils (nacheinander)   und   berechnet. Dazu genügen (für geeignetes  )   Bandzellen für   und   Bandzellen für die Berechnung von   bzw.  . Insbesondere kann eine solche DTM also mit Platzbedarf   ermitteln, ob   und damit, ob  .

Die Wahl geeigneter Konstanten   ist insbesondere wegen   möglich.

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • 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.