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 eine platzkonstruierbare Funktion mit . Dann gilt:

Beweisidee

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

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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.