サヴィッチの定理
サヴィッチの定理(英: Savitch's theorem)とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。f(n) ≥ log(n) であるような任意の関数 f について、次が成り立つとするものである。
NSPACE(f(n)) ⊆ DSPACE(f2(n)).
言い換えれば、非決定性チューリング機械が f(n) の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。
この定理の重要な系として、以下のものがある。
PSPACE = NPSPACE これは、多項式の平方も多項式であることから直接導かれる。多項式時間の複雑性クラス(PとNP)に同様の関係は成り立たないと予想されているが、未解決の問題である。
NL ⊆ L 証明過程から直接導かれる。