Registrieren Passwort vergessen?

Satz von Savitch

2. Mär 2008, 21:00

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.

[Bearbeiten] Formale Definition

Sei s:\mathbb{N}\rightarrow\mathbb{N} eine bandkonstruierbare Funktion mit s(n)\geq\log(n). Dann gilt:

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

[Bearbeiten] Literatur

  • Walter Savitch: Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.
Von „http://de.wikipedia.org/wiki/Satz_von_Savitch“
Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.
In Kooperation mit Lycos Europe Network