Immerman-Szelepcsényi Theorem

即便知道生命临近终结，也要对清晨的到来心怀感激，平静地度过余下的每个夜晚，为自己出生在这个世界而心怀感恩，为还留在这个世界上的人们祈福。

在证明之前，我们还是考虑一下这个定理表达了什么。

语言学中，有一个命题说：

所有人类语言都是上下文相关的 (Context-sensitive)。

而 Context-Sensitive Language (CSL) 恰好就是 NSPACE (n)。即:

$$\textnormal{CSL}=\textnormal{NSPACE}(n)$$

这个定理说明了，上下文相关语言的补，还是上下文相关的。我们来着手证明它。

根据对称性，实际上就要证明一个命题：

$$\forall L\in\textnormal{NSPACE}(S(n)),\bar{L}\in\textnormal{NSPACE}(S(n))$$

而考虑到字符串被 NTM accept，实际上就是有一条通路从 NTM 的 start configuration 到 accept configuration。而要证明的$\bar{L}\in\textnormal{NSPACE}(S(n))$ 定义展开就是：

$$\forall x\in L,\not\exists \textnormal{a path from }C_{start} \textnormal{ to }C_{accept}$$

考虑到对于一个空间复杂度为$S(n)$ 的图灵机，它的 configuration 的数量最多在$2^{O(S(n))}$（参考 Savitch’s Theorem 中的说明）。所以实际上，我们的目标就是找到一个非确定性$\log$ 级别空间复杂度的算法，解决下述问题：

$(s,t)$-UNCONN 问题：给定一个图$G$ 和其中两个结点$s,t$，如果存在一条 path 从$s\rightarrow t$，则输出 NO。否则输出 YES。

之前在 Savitch’s Theorem 中，我们证明了存在一个确定性的$O(\log^2n)$ 空间的算法，解决$(s,t)$-CONN 问题。重新考虑当时的算法，由于确定型图灵机在处理递归时，需要使用栈保存$s\rightarrow u$ 路径上所有的结点，方便下一步深度优先搜索。但对于非确定型图灵机，我们不需要这个栈，而是利用非确定性去猜测。这地方需要仔细理解一下。

譬如$1\rightarrow 2,3$，我们把$1,2$ 压入栈，是因为想着有可能未来某一天要把$2$ 弹出，再去从$1$ 寻找$1\rightarrow 3$。但是对于非确定性图灵机，我们已经 “同时” 从 1 访问到了$2,3$，不需要一个一个访问，也就不需要存储$1$ 了。

我们 “多路并进” 式地往前走，但凡有一个分支到达了终点就接受。

说明，$(s,t)$-CONN 问题在非确定型图灵机上，只需要$O(\log n)$ 的空间复杂度。只需要存储目前走到了哪个结点就好了。

下面我们考虑$O(\log n)$ 的非确定型空间复杂度，去解决$(s,t)$-UNCONN 问题。

一个非常容易的错误就是，为啥我们不能利用 non-deterministism，去齐头并进地从$s$ 开始走，如果有一个分支走到了$t$ 就拒绝？

这是因为，需要仔细思考$(s,t)$-UNCONN 问题的定义，它是一个 **"不存在"的问题，逻辑上等价于" 对于任意 "。而 NTM 的非确定性，是只要有一个分支 accept 就全局 accept，所以解决的是存在 ** 问题。故上述想法是不对的，不能因为某条分支没走到$t$，就认为全局都不可能走到$t$。

（其实上述误区就在于，“怎么把一个 NTM 的 accept 和 reject 交换”。它无法在很低的时间复杂度内完成（$NP=?coNP$ 未知）（因为需要知道所有 branch reject 才能 accept），但可以在很低的空间复杂度内完成$NSPACE=coNSPACE$ 也就是这个定理证明的。）

下面我们考虑一个 nondeterminism 的算法，去计算函数：

$$R(s,t,l)=\begin{cases} 1 & \textnormal{there exists a path from s to t, and its length}\leq l\\ 0 & \textnormal{otherwise} \end{cases}$$

注意，这是一个函数需要计算。即我们设计的 NTM 需要当且仅当一个 branch 输出 0 或 1，而其他 branch 都 reject。

这个算法其实是有点巧妙和令人费解的。这个 NTM 总是 accept 的，只不过 accept 后输出 0 还是 1。我们用这个函数输出去替代 “accept”、“reject”。

要计算$R(s,t,l)$:

1. 非确定性地创建$2^{|V|-1}$ 个 branches，每个 branches 猜测了一个 bit mask（譬如$m=101011$）表示了对于每个$u\in V-\{t\}$，$s\rightarrow u$ 是否存在一条长度$\leq l$ 的 path。$m(u)=1$ 表示猜测有，反之则没有。

2. 对于每一个 branch，以及 bit mask 中为 1（$m(u)=1$）的那些点$u\in V-\{t\}$，我们用$(s,t)$-CONN 的图灵机去判定$s\rightarrow u$ 是否存在一条长度$\leq l$ 的边。

   更具体地，这一步可以直接运行$(s,t)$-CONN 的 NTM，如果该 NTM accept 则状态转移进入第 3 步；如果该 NTM 有任意分支 reject，则全局也 reject，说明这个 branch 的 bit mask 猜错了。

3. 能进入这一步，说明每个$m(u)=1$ 的点$u$ 都猜正确的了。但是对于$m(u)=0$ 的那些点，我们并没有办法得知，是否真的不存在$s\rightarrow u$ 的长度$\leq l$ 的边，因为不存在是困难的。

   我们存下来$\textnormal{count}^*=$ bit mask 中$1$ 的个数。

注意，前三步可以在空间复杂度$O(\log n)$ 内完成。因为我们只关心 bit mask 中 1 的个数，没必要把 bit mask 存下来。

所以实际上是一个一个点$u$ 分支产生$m(u)=0/1$，然后如果$m(u)=1$ 就判定一下，如果正确了，就$\textnormal{count}^*+=1$。

4. 现在假设我们知道了一个数 "$count=s$ 走$\leq l$ 步能到达的点的数量 "。（具体计算方法会在后面讨论）

   （注意，$count$ 和$count^*$ 差异就在于，$count^*$ 是去除了$t$ 后、在当前分支猜测情况下算出来的，不一定是对的，但一定小于等于正确的值，而且一定有一个分支等于正确的值。）

   然后我们讨论：

   • 若$count^*=count$，则 accept 并输出 0。此时$count^*$ 是正确的值，而且$V$ 和$V-\{t\}$ 中，$s$ 走$\leq l$ 步能到达的点的数量是一样的，故输出 0。

   • 若$count^*< count-1$，则直接 reject。说明我们 bit mask 猜错太多了。因为正确的$count^*$ 最少为$count-1$。

   • 若$count^*=count-1$，此时需要分类讨论：

     • 若$s\rightarrow t$ 真的存在一条长$\leq l$ 的 path，则说明$count^*$ 猜测正确，则需要输出 1。
     • 若$s\rightarrow t$ 真的不存在一条长$\leq l$ 的 path，则说明$count^*$ 猜测错误，存在一个点$u$，$s\rightarrow u$ 有一条长$\leq l$ 的 path，但我们把他猜成了$m(u)=0$。

     为了判别以上两种情况，我们直接运行判定$(s,t)$-CONN 的 NTM，去判定是否存在$s\rightarrow t$ 有一条长度$\leq l$ 的 path。若该 NTM accept，则直接输出 1。若该 NTM 任意分支 reject，则全局 reject 这个分支。说明$count^*$ 猜错了，我们期待猜对了的那个分支去输出结果。

综上，可以认识到。所有分支中，$count^*$ 最大的那个分支的猜测结果是正确的。而且$count-1\leq count^*\leq count$。而我们只希望正确的$count^*$ 那个分支输出结果。

下面我们说明整个算法，并且计算$count$:

1
2
3
4
5
6
7

count[0] = 1;
for l = 1 to n
    for u, v in V
        if (u, v) in E && R(s, u, l - 1) == 1 then
            count[l]++;
if R(s, t, n) == 1 then return false;
else return true;

上述算法就在空间复杂性$O(\log n)$ 内解决了$(s,t)$-UNCONN 问题。