Enzyklopädie > S > Satz von Savitch
Satz von Savitch
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.
Mehr Informationen (Wikipedia)
Die Informationen wurden von Wikipedia übernommen, einer offenen Enzyklopädie in welche Freiwillige ihre Beiträge beisteuern.
Die Texte sind unter den Bedingungen der GNU Free Documentation License zugänglich.Encyklopedie (cz) Encyklopédia (sk) Encyclopedia (en)