サビッチの定理

計算複雑性理論 において、1970年にウォルター・サヴィッチによって証明されたサヴィッチの定理^{[ 1 ]}は、決定論的空間複雑性と非決定論的空間複雑性の関係を示している。この定理は、任意の空間構成可能な関数に対して、次の関係が成り立つと述べている。${\displaystyle f\in \Omega (\log(n))}$[ ^{2 ]​}

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).}$

言い換えれば、非決定性チューリングマシンが問題を解くことができる場合、${\displaystyle f(n)}$空間が決定論的である場合、チューリングマシンは、その空間の上限の2乗で同じ問題を解決できます。^{[ 3 ]} 非決定論は時間に関して指数関数的な利益をもたらす可能性があるように見えますが（証明されていない指数時間仮説で形式化されているように）、サビッチの定理は、空間要件への影響は著しく限定的であることを示しています。^{[ 4 ]}

この定理は相対化できる。つまり、任意のオラクルに対して、すべての「チューリングマシン」を「オラクルチューリングマシン」に置き換えても、やはり定理となる。^{[ 5 ]}

この証明は、有向グラフ内の2つの頂点間にパスが存在するかどうかを判定する問題であるSTCONのアルゴリズムに基づいており、実行時間は${\displaystyle O\left((\log n)^{2}\right)}$スペース${\displaystyle n}$頂点。アルゴリズムの基本的な考え方は、頂点からパスが存在するかどうかをテストする、やや一般的な問題を再帰的に解くことです。${\displaystyle s}$別の頂点へ${\displaystyle t}$最大で使用する${\displaystyle k}$エッジ、パラメータの場合${\displaystyle k}$入力として与えられます。STCON はこの問題の特殊なケースで、${\displaystyle k}$は、パスに制限を課さないほど十分に大きく設定されます（たとえば、グラフの頂点の総数、またはそれ以上の値）。${\displaystyle k}$-エッジパスから${\displaystyle s}$に${\displaystyle t}$決定論的アルゴリズムはすべての頂点を反復処理できます${\displaystyle u}$、そして、から半分の長さのパスを再帰的に検索します${\displaystyle s}$に${\displaystyle u}$そして${\displaystyle u}$に${\displaystyle t}$^{[ 6 ]}このアルゴリズムは、擬似コード（ Python構文） で次のように表現できます。

def stcon ( s , t ) -> bool : """s から t への任意の長さのパスが存在するかどうかをテストします""" return k_edge_path ( s , t , n ) # n は頂点の数ですdef k_edge_path ( s , t , k ) -> bool : """s から t までの長さが k 以下であるパスが存在するかどうかをテストします""" if k == 0 : return s == t if k == 1 : return s == t or ( s , t ) in edges for u in vertices : if k_edge_path ( s , u , floor ( k / 2 )) and k_edge_path ( u , t , ceil ( k / 2 )): return True return False

再帰呼び出しごとにパラメータが半分になるため${\displaystyle k}$再帰のレベル数は${\displaystyle \lceil \log _{2}n\rceil }$各レベルには${\displaystyle O(\log n)}$関数引数とローカル変数を格納するためのビット数：${\displaystyle k}$そして頂点${\displaystyle s}$、${\displaystyle t}$、 そして${\displaystyle u}$必要とする${\displaystyle \lceil \log _{2}n\rceil }$ビットずつ。したがって、補助空間の総複雑度は${\displaystyle O\left((\log n)^{2}\right)}$[ ^{6 ]}入力グラフは別の読み取り専用メモリに表現されているとみなされ、この補助的な空間制限には寄与しません。あるいは、暗黙のグラフとして表現することもできます^。上記では高水準言語のプログラムの形で説明しましたが、同じアルゴリズムをチューリングマシン上で同じ漸近的な空間制限で実装することもできます。

このアルゴリズムは、与えられた空間制限内で動作する非決定性チューリングマシンとそのテープの構成を頂点とする暗黙的グラフに適用できる。${\displaystyle f(n)}$このグラフのエッジは、機械の非決定論的な遷移を表しています。${\displaystyle s}$マシンの初期設定に設定され、${\displaystyle t}$は、すべての受理停止状態を表す特別な頂点に設定されます。この場合、アルゴリズムは、マシンが非決定的な受理パスを持つ場合に true を返し、そうでない場合は false を返します。このグラフの構成数は${\displaystyle O(2^{f(n)})}$このことから、この暗黙のグラフにアルゴリズムを適用すると空間が消費されることがわかる。${\displaystyle O(f(n)^​​{2})}$。このように、非決定性チューリングマシンの構成を表すグラフの接続性を決定することで、チューリングマシンが使用する空間の二乗に比例する空間で、そのマシンが認識する言語への所属を決定できる。^{[ 6 ]}

この定理の重要な系には以下のようなものがある。

PSPACE = NPSPACE

つまり、決定性多項式空間チューリングマシンと非決定性多項式空間チューリングマシンで認識できる言語は同じである。これは、多項式関数の二乗が依然として多項式関数であるという事実から直接導かれる。^{[ 6 ]}多項式時間複雑性クラスPとNPの間には同様の関係は存在しないと考えられているが、これはまだ未解決の問題である。

NL ⊆ L ²

つまり、対数空間で非決定的に解ける言語はすべて、複雑性クラスで決定的に解ける。$$\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right).}$$これは、STCONがNL完全であるという事実から導かれる。

• イマーマン・セレプチェニの定理– 補元による非決定性空間の閉包 

• ランス・フォートナウ著、『複雑性の基礎』、第18課：サビッチの定理。2009年9月9日アクセス。
• リチャード・J・リプトン著『サヴィッチの定理』。証明がどのように発見されたかについての歴史的解説が記されている。