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

Immerman-Szelepcsényi Theorem: For any function S(n)lognS(n)\geq \log n,

NSPACE(S(n))=co-NSPACE(S(n))\textnormal{NSPACE}(S(n))=\textnormal{co-NSPACE}(S(n))

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

语言学中,有一个命题说:

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

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

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

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


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

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

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

xL,∄a path from Cstart to Caccept\forall x\in L,\not\exists \textnormal{a path from }C_{start} \textnormal{ to }C_{accept}

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

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

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

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

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

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


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

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

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

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

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

R(s,t,l)={1there exists a path from s to t, and its lengthl0otherwiseR(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)R(s,t,l):

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

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

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

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

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

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

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

  1. 现在假设我们知道了一个数 "count=scount=sl\leq l 步能到达的点的数量 "。(具体计算方法会在后面讨论)

    (注意,countcountcountcount^* 差异就在于,countcount^* 是去除了tt 后、在当前分支猜测情况下算出来的,不一定是对的,但一定小于等于正确的值,而且一定有一个分支等于正确的值。)

    然后我们讨论:

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

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

    • count=count1count^*=count-1,此时需要分类讨论:

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

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

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

下面我们说明整个算法,并且计算countcount:

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(logn)O(\log n) 内解决了(s,t)(s,t)-UNCONN 问题。