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