makenowjust-labs/blog

Immerman-Szelepcsényiの定理は $s(n) \ge \log n$ の場合に $\mathbf{NSPACE}(s(n))$ (テープ長に上限のある非決定性チューリングマシンが受理できる言語のクラス) が、否定について閉じていることを示す定理です。 Neil ImmermanとRóbert Szelepcsényiが1987年にそれぞれ独立して示し、この成果により両者は1995年にGödel賞を受賞しました。 このように、Immerman-Szelepcsényiの定理は、計算量複雑性の理論上とても重要な定理となっています。

Immerman-Szelepcsényiの定理の証明は、テープ長に上限のある非決定性有限チューリングマシン (NTM) の様相 (configuration) の総数が入力の長さとそのNTMの大きさで抑えられることを活かして、次のようなNTMを構成することで実現されます。

• ある様相から到達可能な様相の総数を数え上げた上で、
• その総数のステップ中に、受理状態に到達可能かを判定する。

この記事ではImmerman-Szelepcsényiの定理を[Uezato, 2024]を参考に証明したいと思います。 方針は論文に書いてある通りで特に目新しい部分はありません。自分の備忘録として残しておきます。

想定読者: 情報科学の基本的な部分を理解しており、計算量複雑性の理論などに関心があることを想定しています。