サヴィッチの定理

ウィキペディア

サヴィッチの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/04/30 08:06 UTC 版)

サヴィッチの定理（英: Savitch's theorem）とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。f(n) ≥ log(n) であるような任意の関数 f について、次が成り立つとするものである。

NSPACE(f(n)) ⊆ DSPACE(f²(n)).

言い換えれば、非決定性チューリング機械が f(n) の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。

証明

この証明は構築的に行われる。まず、STCON問題（有向グラフの2点間の経路の有無を問う問題）のアルゴリズムとして、n 個のノードからなるグラフについて log²(n) の領域を要する方式を示す。次にこれを用いて、開始ノードから受容ノードまでの経路があるかどうかを決定する非決定性機械の計算機（非決定性チューリング機械の計算経路からなる木構造）に対応したアルゴリズムを実行する決定性機械を構築する。STCON問題はNL完全なので、以上から NL に属する全問題が L² に属することが示される。

系

この定理の重要な系として、以下のものがある。

• PSPACE = NPSPACE
  • これは、多項式の平方も多項式であることから直接導かれる。多項式時間の複雑性クラス（PとNP）に同様の関係は成り立たないと予想されているが、未解決の問題である。
• NL ⊆ L²
  • 証明過程から直接導かれる。

参考文献

• Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 8.1: Savitch's Theorem, pp.279–281.
• Christos Papadimitriou (1993年). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1.  Pages 149–150 of section 7.3: The Reachability Method.
• W.J.Savitch, "Relationship between nondeterministic and deterministic tape classes", J.CSS, 4, pp 177-192, 1970