makenowjust-labs/blog

makenowjust-labs/blog

MakeNowJust Laboratory Tech Blog

Immerman-Szelepcsényiの定理について

2024-06-27 (更新: 2024-07-08) / 読むのにかかる時間: 約14.6分
オートマトン理論
8
計算量複雑性
1

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

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

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

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

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

準備

非決定性チューリングマシン (NTM)

非決定性チューリングマシン (Nondeterministic Turing Machine, NTM) として、cc-bounded kk-working-tapes log-space NTM M=(k,c,Q,qinit,QF,Σ,Γ,□,Δ)M = (k, c, Q, q_{\mathrm{init}}, Q_F, \Sigma, \Gamma, \Box, \Delta) を定義します2。 MMの各要素は次のような意味になります。

  • kkは作業テープ (working tape) T1,T2,…,TkT_1, T_2, \dots, T_kの数です。
  • ccはテープ長の上限のための定数で、各テープの長さは C=⌈clog⁡∣w∣⌉C = \lceil c \log |w| \rceil (wwは入力文字列、 ⌈x⌉\lceil x \rceil は天井関数) によって抑えられます。
  • QQは状態の有限集合で、qinit∈Qq_{\mathrm{init}} \in Qは初期状態、QF⊆QQ_F \subseteq Qは受理状態の集合になります。
  • Σ\Sigmaは入力のアルファベットで、Γ\Gammaはテープのアルファベット、□∈Γ\Box \in \Gammaは作業テープの空の部分を埋めるための記号です。
  • Δ\Deltaは遷移規則で、各規則は p→τ∣θqp \xrightarrow{\tau | \theta} q もしくは p→κ↦κ′∣θqp \xrightarrow{\kappa \mapsto \kappa' | \theta} q という形を取ります (ここで p,q∈Qp, q \in Q, τ∈Σ∪{⊢,⊣}\tau \in \Sigma \cup \{ \vdash, \dashv \}, κ,κ′∈Γ∪{⊢,⊣}\kappa, \kappa' \in \Gamma \cup \{ \vdash, \dashv \}, θ∈{−1,+1,0}\theta \in \{ -1, +1, 0 \})。

w∈Σ∗w \in \Sigma^\ast を入力文字列とします。 MM上の文字列 ⊢w⊣\vdash w \dashv で有効な様相 (valid configuration) とはタプル ⟨q,i,(T1,i1),(T2,i2),…,(Tk,ik)⟩\langle q, i, (T_1, i_1), (T_2, i_2), \dots, (T_k, i_k) \rangle のことで、それぞれの値は次のような意味です。

  • q∈Qq \in Q は現在の状態、i∈Ni \in \mathbb{N} (0≤i≤∣w∣+20 \le i \le |w| + 2) は文字列 ⊢w⊣\vdash w \dashv 上の位置を表します。
  • 各 x∈{1,2,…,k}x \in \{ 1, 2, \dots, k \} について (Tx,ix)(T_x, i_x) は、
    • Tx∈(⊢ΓC⊣)T_x \in (\vdash \Gamma^C \dashv) は xx 番目の作業テープを表します (CC は上で定義しました)。
    • ix∈Ni_x \in \mathbb{N} (0≤ix≤C+20 \le i_x \le C + 2) は xx 番目の作業テープのヘッドの位置を表します。

MM上の文字列⊢w⊣\vdash w \dashvで有効な様相全体からなる集合を ValidM(w)\mathbf{Valid}_M(w) と書くことにします (また、MM を省略して Valid(w)\mathbf{Valid}(w) とします)。 有効な様相の定義から、Valid(w)\mathbf{Valid}(w) の大きさは cc (C=c⌈log⁡∣w∣⌉C = c \lceil \log |w| \rceil) と kk と入力文字列の長さ ∣w∣|w| で次のように計算できます。

∣Valid(w)∣=∣Q∣×(∣w∣+2)×(∣Γ∣C×(C+2))k|\mathbf{Valid}(w)| = |Q| \times (|w| + 2) \times (|\Gamma|^C \times (C + 2))^k

入力文字列 ww について、I(w)\mathcal{I}(w) を文字列 ⊢w⊣\vdash w \dashv での初期様相として、次のように定義します。

I(w)=⟨qinit,0,(⊢□C⊣,0),(⊢□C⊣,0),…,(⊢□C⊣,0)⟩\mathcal{I}(w) = \langle q_{\mathrm{init}}, 0, (\vdash \Box^C \dashv, 0), (\vdash \Box^C \dashv, 0), \dots, (\vdash \Box^C \dashv, 0) \rangle

ξ=⟨q,i,(T1,i1),…,(Tk,ik)⟩\xi = \langle q, i, (T_1, i_1), \dots, (T_k, i_k) \rangle を文字列 ⊢w⊣\vdash w \dashv で有効な様相とします。 遷移規則 δ∈Δ\delta \in \Delta について、有効な様相での遷移関係 ⇒δ\xRightarrow{\delta} を次のように定義します。

δ=p→τ∣θq∈Δ(⊢w⊣)[i]=τξ⇒δ⟨q,i+θ,(T1,i1),…,(Tk,ik)⟩\frac {\delta = p \xrightarrow{\tau | \theta} q \in \Delta \qquad (\vdash w \dashv)[i] = \tau} {\xi \xRightarrow{\delta} \langle q, i + \theta, (T_1, i_1), \dots, (T_k, i_k) \rangle} δ=p→κ↦κ′∣θq∈Δκ=Tx[ix]ξ⇒δ⟨q,i,(T1,i1),…,(Tx[ix]≔κ′,ix+θ),…,(Tk,ik)⟩\frac {\delta = p \xrightarrow{\kappa \mapsto \kappa' | \theta} q \in \Delta \qquad \kappa = T_x[i_x]} {\xi \xRightarrow{\delta} \langle q, i, (T_1, i_1), \dots, (T_x[i_x] \coloneqq \kappa', i_x + \theta), \dots, (T_k, i_k) \rangle}

ここで Tx[ix]≔κ′T_x[i_x] \coloneqq \kappa' は TxT_x の ixi_x 番目の位置に κ′\kappa' を書き込んだ新しいテープを表します。 また、遷移規則 δ∈Δ\delta \in \Delta は省略されて単に ⇒\Rightarrow と書かれる場合があり、さらにこの推移的閉包を ⇒∗\Rightarrow^\ast と書きます。

cc-bounded kk-working-tapes log-space NTM 全体からなる集合を NLOG(c,k)\mathbf{NLOG}(c, k) と書くことにします。 cc と kk が重要ではない場合、単に NLOG\mathbf{NLOG} と書くことがあります。

M∈NLOGM \in \mathbf{NLOG} と文字列 ww について、M(w,ξ)M(w, \xi) を ⊢w⊣\vdash w \dashv 上での ξ\xi から到達可能な、有効かつ受理される様相全体からなる集合とします。 つまり、M(w,ξ)M(w, \xi) は次のような集合になります。

M(w,ξ)={ξ′∣ξ⇒∗ξ′, ξ′=⟨qacc,i,T⟩, qacc∈QF}M(w, \xi) = \{ \xi' \mid \xi \Rightarrow^\ast \xi',\, \xi' = \langle q_\mathrm{acc}, i, T \rangle,\, q_\mathrm{acc} \in Q_F \}

さらに、MM の受理する言語 L(M)L(M) を M(w,ξ)M(w, \xi) を用いて、 L(M)={w∣M(w,I(M))≠∅}L(M) = \{ w \mid M(w, \mathcal{I}(M)) \ne \emptyset \} と定義します。

NLOG\mathbf{NLOG} について、Immerman-Szelepcsényiの定理を示すにあたって用いる命題をいくつか述べておきます。

Immerman-Szelepcsényiの定理

まず始めに、Immerman-Szelepcsényiの定理のステートメントを確認します。

ここで重要な考察として、s(n)s(n)-bounded NTMの有効な様相の総数は NLOG(c,k)\mathbf{NLOG}(c, k) の場合と同様に s(n)⌈log⁡∣w∣⌉s(n) \lceil \log |w| \rceil の適当な定数倍の長さのテープで数えられるということです。 よって NSPACE(log⁡n)=co-NSPACE(log⁡n)\mathbf{NSPACE}(\log n) = \mathbf{co}\text{-}\mathbf{NSPACE}(\log n)、つまり NLOG=co-NLOG\mathbf{NLOG} = \mathbf{co}\text{-}\mathbf{NLOG} により、 Immerman-Szelepcsényiの定理を示すことができます。

証明

というわけで、証明の方針を説明します。

M∈NLOG(c,k)M \in \mathbf{NLOG}(c, k) について、L(M‾)=Σ∗∖L(M)L(\overline{M}) = \Sigma^\ast \setminus L(M) であるような M‾∈NLOG(O(c⋅k),k+∂)\overline{M} \in \mathbf{NLOG}(O(c \cdot k), k + \partial) を構成することで、定理を示すことができます。 ここで ∂\partial は MM に依存しない定数です。

では M‾\overline{M} はどのように構成するのかというと、次の二段階に分けて行います。

  1. ある様相 START\mathrm{START} から到達可能な様相の総数 CC を計算する。
  2. その CC ステップ以内に到達できる様相の中に受理状態のものがあるかを調べる。

そして、これらは ∣Valid(w)∣|\mathbf{Valid}(w)| までの数値を記録できる ∂\partial 個の変数を使って NTM で計算できます。 具体的な方法は[Uezato, 2024]のLemma 11で疑似コードを使って説明しています。 また、1については[Immerman, 1988]のLemma 2で、2についてはLemma 1で詳細に説明されています。

あとがき

今回はImmerman-Szelepcsényiの定理について説明しました。 すごく有名な定理ではありませんが、計算量複雑性の理論では重要な定理だと思います。

例えば、プッシュダウンオートマトン (文脈自由言語) は否定について閉じていません。 一方、有限状態オートマトン (正規言語) や線形拘束オートマトン (文脈依存言語) は否定について閉じています3。 このように否定について閉じているかはチョムスキー階層の上下に依存するものではありません。 Immerman-Szelepcsényiの定理は、この疑問に対して、この程度の計算力があれば否定について閉じている、と言える根拠を与えるものだと考えられます。

また、この定理の証明はとても構成的なことも興味深いところだと思います。 具体的に、あるNTMの言語の補言語を受理するNTMの構成の方法が説明されているので、実際にそのようなNTMを構成してみたら面白いのではないかと考えています。 しかし、説明している方法をそのまま行っても、およそ現実的な時間では計算できないと思うので、効率的に計算するにはどうしたらいいのか、というのも気になっています4。

自分がImmerman-Szelepcsényiの定理に興味を持ったのは[Uezato, 2024]を読んだためでした。 この論文では、肯定・否定先読みと後方参照を持つ正規表現の言語クラスが NLOG\mathbf{NLOG} と一致することを示しています。 その中で、オラクルによって多重にネストしたNTMを1重に潰すのに、このImmerman-Szelepcsényiの定理を用いています。 これも面白い話だったので、この話もいつかできたらと思います。

それでは、最後まで目を通していただきありがとうございました。

参考文献

[Uezato, 2024]:

Uezato, Yuya. "Regular Expressions with Backreferences and Lookaheads Capture NLOG." arXiv preprint arXiv:2404.17492 (2024).

https://arxiv.org/abs/2404.17492

[Immerman, 1988]:

Immerman, Neil. "Nondeterministic space is closed under complementation." SIAM Journal on computing 17.5 (1988): 935-938.

https://ieeexplore.ieee.org/document/5270

[Kuroda, 1964]

Kuroda, S-Y. "Classes of languages and linear-bounded automata." Information and control 7.2 (1964): 207-223.

https://www.sciencedirect.com/science/article/pii/S0019995864901202

脚注

  1. セレプチェーニと発音するみたい？ (参考: これの最後のスライド) ↩

  2. kk 本の作業テープを持っていますが、区切り用の文字を追加して1本のテープに並べることができるので、言語クラスは作業テープが1本のNTMと変わらないはずです。 ↩

  3. 文脈依存言語の計算クラスは NSPACE(n)\mathbf{NSPACE}(n) に等しいことが知られています (参考: [Kuroda, 1964])。 ↩

  4. とはいえ、NLOG\mathbf{NLOG} や NSPACE\mathbf{NSPACE} 自体があまり現実的な時間で計算できると考えられる計算クラスではないです。 ↩