Satz von Savitch
aus Wikipedia, der freien Enzyklopädie
Der Satz 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 
eine bandkonstruierbare Funktion mit 
. Dann gilt:
- NSPACE(s(n))
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.
