Savitch's Theorem

只有在接下了苦涩之杯后，才能得到永远的生命

这个定理的证明实际上基于一个算法，也很好说明了 complexity 和 algorithm 间的关系。

考虑这样一个问题，给定一个图$G$，以及两个顶点$s,t$，判断$G$ 中是否从$s$ 到$t$ 有一条通路。这个问题被称为 STCON 问题，可在空间复杂度$O(log^2n)$ 内解决。算法如下：

1
2
3
4
5
6
7
8

bool k_edge_path(s, t, k){
	if (k == 0) return s == t;
	if (k == 1) return (s, t) in Edge(G);
	for u in Vertex(G){
        if k_edge_path(s, u, k - 1) && k_edge_path(u, t, k - 1) return true;
    }	
    return false
}

这段代码就是求解$s\rightarrow t$ 是否有长度$\leq 2^k$ 的路径，使用了倍增的思想。正确性是显然的，主要考虑它的空间复杂性。

既然使用了递归，那么就需要一个栈实现。首先整个递归深度为$O(log(n))$，因为$s\rightarrow t$ 的路径最长可能是$n$。

然后每层递归都需要存储$s,t,k$ 三个变量，而这三个变量相对于输入$\langle G,s,t\rangle$ 的长度来说，存储空间都是$O(log(n))$ 级别的。

故整个算法空间复杂度为$O(log^2n)$ 的。

为什么要考虑这个问题呢？就是因为图和非确定性图灵机的同构关系。

一个非确定性图灵机，假如我们限制它的空间复杂度在$f(n)$ 级别，那么所有可能的 configuration 有多少个呢？

• 带子上的内容最多有$O(2^{f(n)})$ 级别个。
• 状态数是常量个，不依赖于输入。
• 读写头的位置有$O(f(n))$ 个。

一个 configuration 包含且仅包含上述内容，故给定一个 NTM，它的 configuration 最多在$O(f(n)\cdot 2^{f(n)})$ 级别。

而 NTM 运行的过程，实际上可以看作一个图。（不是把 NTM 本身看作一个图！）其中结点是 configuration，而边是 nondeterministic 的转移。而最后是否 accept 就是在寻找是否存在一条 path，从初始到 accept configuration。故利用上述算法，可以得到需要的空间复杂度为：

$$O(log^2(f(n)\cdot 2^{f(n)}))=O(f(n)^2)$$

故$NSPACE(f(n))\subseteq DSPACE(f(n)^2)$。同理，利用 BFS、DFS 等不考虑空间但节省时间的算法，也可以得到时间复杂度为指数级别。

这个证明可能略粗糙，主要揭示了一个思想，有很多细节问题。譬如为啥我们不需要枚举$t\in accept\;configuration$？实际上不失一般性，我们可以在不增加时间空间复杂度的情况下，修改 NTM 使得它只有一个 accept configuration。其他还有问题可以发挥下主观能动性解决下 ww