Relationships Between Nondeterministic and Deterministic Tape Complexities - 昏論会ウィキ

Relationships Between Nondeterministic and Deterministic Tape Complexities

サヴィッチの定理 の初出論文です。

Theorem 1

な関数があって、非決定性チューリングマシンを使って な空間計算量で解ける問題は、決定性チューリングマシンで な空間計算量で解ける。

系： PSPACE = NPSPACE、などなど

証明

• その非決定性TMを ZN とする。入力の長さを n とする。
• ZN はメモリを f(n) の定数倍しか使わないので、ZNの計算途中の特定時点のメモリの状態は f(n) の定数倍くらいあれば表現できる。
  • これを R とする。
• ZNの取り得るメモリの状態はしかないので、ZNの(停止する)計算はステップあれば終われる

というわけで、決定性マシンを使って

• ZNの終了状態っぽい状態を全列挙
  • サイズRの状態全列挙は、多倍長整数を1ずつ増やしていくと考えれば、O(R) の空間計算量でできる。
• それぞれについて、「初期状態から ステップ以内で行けるか？」を判定する
  • 行ければその計算結果を返す

state simulate_ZN() {
  state ini = ZNの初期状態;
  foreach(s ∈ 可能な状態全列挙)
    if( ikeru(ini, s, 2^R) )
       return s;
}

最後の判定をする関数を、こう定義する

bool ikeru(state ini, state fin, int steps) {
  if( steps == 0 )
     return ini == fin;
  if( steps == 1 )
     return ini==fin || 頑張ってZNの遷移関数をチェック;
  foreach(s ∈ 可能な状態全列挙)
     return ikeru(ini, s, steps/2) && ikeru(s, fin, (steps+1)/2);
}

分割統治。

• 再帰は ステップで終わるので、必要なスタックの深さは R 段。
• 各再帰ステップでstate型の変数は3個くらいしかでてきてないので、 くらいメモリあればできる

証明終わり。決定性TMで 空間で判定できている。

注意事項

• という制約がつくのは何故か？
  • ないと、「入力のどこを読んでいる最終か？」というポインタがstate型に収まらないので困るので
• 正確には、 がちゃんと計算可能であることを示さないと上の議論は完成しない。
  • f(n) が計算不可能関数の時は、f(n)≦1 と仮定、f(n)≦2 と仮定、f(n)≦4 と仮定、と指数的にサイズ増やして試し直すトリックを使えば大丈夫

系3

を対数or多項式or指数関数とするの空間計算量の非決定性チューリングマシンを同じの決定性チューリングマシンでシミュレートできるなら、より大きいすべての関数で同じことが起きる

• 一カ所D=Nに潰れればぜんぶつぶれる。
• これは、「だから(例えば)DSPACE(n)≠NSPACE(n)ではないだろう」と思っている研究者と「だから大体どのfでもDSPACE(f(n))=NSPACE(f(n))だろう」と思っている研究者の割合はどのくらいなんだろう。