サヴィッチの定理
サヴィッチの定理（英: Savitch's theorem）とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。"f"("n") ≥ log("n") であるような任意の関数 "f" について、次が成り立つとするものである。
言い換えれば、非決定性チューリング機械が "f"("n") の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。