Immerman-Szelepcsényiの定理
Immerman-Szelepcsényi's theorem
イマーマン-セレプチェーニの定理？
定理（Immerman-Szelepcsényi）
$ \textbf{NSPACE}(S) = \textbf{co-NSPACE}(S)
定義
$ s \in V(G)について
$ C_i(s) \coloneqq \{z \in G | (s, z) \in E(G)^i\}
頂点$ sから$ i本の辺を辿って到達できる頂点の集合
定理
$ \overline{\mathsf{PATH}} \in \textbf{NL}
Proof.
任意の$ (G, s, t)について以下を満たすTM$ Aが存在すれば良い $ \braket{G, s, t} \in \overline{\mathsf{PATH}} \iff \exists_{u\colon \text{read-once certificate}}[A(\braket{G, s, t}, u) = 1]
Proof.
$ i = 0のとき
各$ v \in E(V)について
$ v \in C_0(s) \iff v = s
よって
$ |C_0(s)| = |\{s\}| = 1
この量化子の動く範囲は$ \le m = O(n)だからLで計算できる $ i + 1のとき
各$ v \in V(G)について
$ v \in C_{i+1}(s) \iff \exists_{w_1, w_2, ..., w_i \in V(G)}[(s, w_1), (w_1, w_2), ..., (w_i, v) \in V(G)]
$ v \notin C_{i+1}(s) \iff \exists_{z^1_1, ..., z^1_i, z^2_1, ..., z^2_i, ..., z^{|C_i(s)|}_1, ..., z^{|C_i(s)|}_i \in V(G)}
$ [z^1_i < z^2_i < ... < z^{|C_i(s)|}_i
$ {} \land \forall_{1 \le k \le |C_i(s)|}[(s, z^k_1), (z^k_1, z^k_2), ..., (z^k_{i-1}, z^k_i) \in E(G)]
$ {} \land \forall_{w \in V(G)}[(w, v) \in E(G) \implies \forall_k[z_k \ne w]]]
certificate：$ |[z^1_1, ..., z^1_i, z^2_1, ..., z^2_i, ..., z^{|C_i(s)|}_1, ..., z^{|C_i(s)|}_i]| \le O(i(\log n)^2) 各$ v \in V(G)について$ v \in C_{i+1}(s)かどうかを調べ, そうならばインクリメントして$ |C_{i+1}(s)|を数える
$ i = |V(G)|のとき$ t \in C_i(s)を調べれば良い
系
$ \textbf{coNL} = \textbf{NL}
Proof.
系
$ \textbf{NSPACE}(S) = \textbf{co-NSPACE}(S)
Proof.
$ L \in \textbf{coNSPACE}(S)は頂点数$ 2^{O(S(n))}のconfiguration graphの$ \overline{\mathsf{PATH}}問題であり上の定理より$ O(\log 2^{O(S(n))}) = O(S(n))の空間で計算できる よって$ \textbf{coNSPACE}(S) \subseteq \textbf{NSPACE}(S)
$ L \in \textbf{NSPACE}(S)とすると$ \overline{L} \in \textbf{coNSPACE}(S) \subseteq \textbf{NSPACE}(S), よって$ \overline{\overline{L}} = L \in \textbf{coNSPACE}(S)
参考