サヴィッチの定理

サヴィッチの定理

サヴィッチの定理は、計算量理論における重要な結果であり、1970年にウォルター・サヴィッチによって証明されました。この定理は、特定の条件下で非決定性チューリング機械と決定性チューリング機械の計算資源に関する関係を示しています。具体的には、任意の関数 f(n) が次の条件を満たすとき、すなわち f(n) ≥ log(n) である場合、以下の関係が成り立ちます。

[NSPACE]) ⊆ [DSPACE])

この式は、非決定性チューリング機械が f(n) の領域を利用して問題を解決できるならば、通常の決定性チューリング機械も同じ問題を解くことができ、その場合には平方の領域を利用すれば目的が達成されることを意味します。非決定性によって時間が劇的に短縮される可能性がある一方で、領域の効率化はそれほど顕著ではないという点にも注意が必要です。

証明

サヴィッチの定理の証明は構築的アプローチで行われます。まず、STCON問題（有向グラフのノード間に経路が存在するかを問う問題）について、n個のノードからなるグラフで log2(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.

サヴィッチの定理は、計算機科学の基礎的な理論の一部として、多くの研究や応用に影響を与え続けています。

もう一度検索