Savitch 定理 | Codeboy's Blog

形式陈述

若 $s:\mathbb N\to\mathbb N$ 空间可构造，且 $s(n)\ge\log n$ ，则

\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(s(n)^2).

这里的非确定空间类 NSPACE要求每条计算分支都遵守工作空间预算，确定空间类 DSPACE则只允许确定性计算。定理表示每个能用非确定性 $O(s(n))$ 工作空间判定的语言，都能用确定性 $O(s(n)^2)$ 工作空间判定。这里采用可构造性与对数下界作为充分条件：模拟机能在预算内安排配置编码和枚举，而输入头位置也能纳入配置长度；并不声称这两个条件在所有强化版本中都不可放宽。常用的 $\log n,n,n^k$ 满足本页条件，小输入按至少一个工作格处理。

从工作空间得到有限配置图

固定输入 $x$ ，令 $n=|x|$ ，并固定一台判定语言的非确定机器 $M$ 。输入带只读，工作带数、字母表和有限状态数均固定，每条分支使用 $O(s(n))$ 个工作格。配置必须同时记录有限状态、工作带内容、所有工作头位置和输入头位置。内容占 $O(s)$ 位，工作头占 $O(\log s)$ 位，输入头占 $O(\log n)$ 位，因此总长为 $O(s+\log n)=O(s)$ 。输入字符本身不复制进配置，检查转移时回到只读输入读取。

取足够大的固定常数 $c$ ，以 $b=\lceil cs(n)\rceil$ 位编码一份配置，允许固定填充。至多有 $C=2^b$ 个编码。枚举所有 $b$ 位串时，需要筛掉状态、头位置、带符号或填充不合法的串；“合法配置”不要求从起点可达。以这些合法配置为顶点，以 $M$ 的一步合法转移为边，便得到输入 $x$ 的配置有向图。本页允许自环，即弧集可为 $V\times V$ 的任意子集，邻接矩阵的对角位也可以为 $1$ 。算法只需检验候选配置和边，不必把整张图写入工作带。

若 $M(x)$ 有接受计算，就能删除路径中重复配置之间的回路，得到长度小于 $C$ 的接受路径。于是只需解决一个有长度上限的可达性问题。对合法配置 $u,v$ 定义

R(u,v,i)=1\iff u\text{ 到 }v\text{ 有长度至多 }2^i\text{ 的路径}.

零长度路径允许存在。基例为 $R(u,v,0)=[u=v\text{ 或 }u\to v]$ ；对于 $i>0$ ，递归式为

R(u,v,i)=\bigvee_{m\in\mathcal C_x} \bigl(R(u,m,i-1)\land R(m,v,i-1)\bigr).

确定性执行时按编码顺序枚举合法 $m$ 。先算左项；左项为假便换下一个 $m$ ，左项为真才算右项；两项为真立即返回真，全部候选失败才返回假。顶层顺序枚举所有合法接受配置 $a$ ，计算 $R(c_{\rm start},a,b)$ ；其中任何一次为真就接受，否则拒绝。多个接受配置不需要同时保存，只增加一个 $O(s)$ 位目标编号。

递归式为什么正确

按 $i$ 归纳。 $i=0$ 时允许至多一步，恰好覆盖同点的零步路径与一步边。假设较小参数正确，考虑一条长度 $L\le2^i$ 的 $u$ 到 $v$ 路径。取路径上第 $\min(L,2^{i-1})$ 步处的顶点为 $m$ ：前段至多 $2^{i-1}$ 步，后段也至多 $2^{i-1}$ 步。若原路径短于半程，则 $m=v$ ，后段是零长度路径。由归纳假设，两次子调用都返回真，因此枚举必能发现一个成功中点。

反过来，若某个中点使两个子调用都返回真，归纳假设给出两条长度各至多 $2^{i-1}$ 的路径。把它们在 $m$ 处连接，长度至多 $2^i$ ，所以返回真必有实际路径。有限的候选枚举与严格下降的 $i$ 保证每次调用终止，顶层接受配置枚举也有限；结合去环论证，这就是一个总停机的确定性判定器。

直觉

配置图可能很大，但一个顶点编号很短。保存完整路径会把“很长的路径”搬进工作带；中点递归只保存“现在正在检查哪两个端点、哪个候选中点”。路径长度每层减半，深度为 $O(\log C)=O(s)$ ，一层仅需 $O(s)$ 位。

关键动作发生在左子调用返回之后。它占用的所有子帧都可以释放，父帧只记一个真值；右子调用随后覆盖同一片工作区。换到下一个中点时再次复用这些格子。算法没有 visited 数组，也没有缓存所有子问题答案，所以空间递推是

S(i)\le S(i-1)+O(s),\qquad S(0)=O(s),

而非两倍子空间或候选数倍子空间。父帧必须保留端点、中点、层号、执行阶段和返回位，这些不能在记账中省略；但已经返回的递归分支也不能继续算作活跃空间。由 $i\le b=O(s)$ 得 $S(b)=O(s^2)$ 。

八顶点图的中点搜索只保留四个活跃帧，左右子调用按时间顺序复用同一工作区 — 中点递归的四帧空间与顺序复用

例子与边界

八顶点图：失败中点也必须检查

取顶点 $\{0,1,\ldots,7\}$ ，边为

0\to1\to2\to3\to4\to5\to6,\qquad 0\to7,\qquad7\to7.

源点为 $0$ ，目标为 $6$ 。八点图若可达，必有至多七步的简单路径，故检查 $R(0,6,3)$ 足够；它允许至多八步，并不要求走满八步。约定所有调用都按 $m=0,\ldots,7$ 枚举，左假时跳过右项，两项真时立即返回。下表列出所有候选的数学真值；真实顶层执行在 $m=2$ 处结束。

顶层中点	左段 $R(0,m,2)$	右段 $R(m,6,2)$	原因与执行情况
0	真	假	左段零步；右段最短六步，超过四步
1	真	假	右段最短五步，超过四步
2	真	真	左段两步、右段四步；首个成功中点
3	真	真	两段各三步；顶层已返回，不再检查
4	真	真	左四步、右两步；顶层已返回
5	假	真	左段最短五步；顶层已返回
6	假	真	左段最短六步，右段零步；顶层已返回
7	真	假	可以进入自环，却不能到达目标；顶层已返回

再展开成功候选，验证递归确实落到基例。左侧 $R(0,2,2)$ 的首个成功中点是 $0$ ，因为 $R(0,0,1)$ 为真，而 $R(0,2,1)$ 在中点 $1$ 处分解成边 $0\to1$ 和 $1\to2$ 。右侧 $R(2,6,2)$ 的首个成功中点是 $4$ ： $R(2,4,1)$ 用中点 $3$ 分成两条边， $R(4,6,1)$ 用中点 $5$ 分成两条边。这里既出现零长子路径，也出现恰好达到子预算的路径。

四帧账本与复用时刻

在左侧深入到基例的一刻，活跃栈如下。表中父帧的阶段说明返回之后该做什么，而不只是列出数学参数。

深度	当前调用	中点与阶段
1	$R(0,6,3)$	$m=2$ ，等待左子调用
2	$R(0,2,2)$	$m=0$ ，左项已真，等待右子调用
3	$R(0,2,1)$	$m=1$ ，等待左子调用
4	$R(0,1,0)$	基例检查边，准备返回真

第四帧返回后，第三帧保留“左真”这一位，再用原第四帧的位置计算 $R(1,2,0)$ 。第三帧返回后，第二帧的子工作区也可以回收。最终顶层左项返回真时，深度二至四的位置全部可被 $R(2,6,2)$ 及其后代覆盖。顶层 $m=0,1$ 的失败探索已经结束，也不再占用额外帧。

一个便于手算的教学布局为每帧统一预留 $u,v,m$ 各三位、 $i$ 两位、阶段两位、结果一位，共十四位；基例也预留同样槽位，四帧共五十六位载荷。只读邻接矩阵的六十四位不计入工作空间，但矩阵扫描位置、栈索引和具体机器控制仍须另计；五十六位不是整台图灵机的精确空间。一般 $N$ 点图用 $O(\log N)$ 位一帧、 $O(\log N)$ 帧，才是与编码细节无关的平方对数结论。

删除一条边后的否实例

现在删除 $4\to5$ ，其余边不变。先独立计算从 $0$ 可达的集合，得到 $\{0,1,2,3,4,7\}$ ，因此 $6$ 不可达。再用中点递归验证：对 $m=0,1,2,3,4,7$ ，左段至多四步可达，但右段都不能到 $6$ ；对 $m=5,6$ ，左段已经不可达，右项无需执行。所有候选均失败，所以 $R(0,6,3)$ 返回假。

这个变式需要穷尽顶层候选，却仍最多同时保留四帧。迁移练习可以继续改为询问 $R(0,4,2)$ ：只允许四步，首个成功中点是 $2$ ，最大活跃帧数降为三。判断空间时应重算递归深度，而不是把前一题访问过的中点数量累加进去。

时间上界与模型条件

复用空间会失去旧答案，因此相同子问题可能被重复计算。令 $P(n+s)$ 为配置合法性、枚举、一步转移等操作的多项式时间上界。标准顺序只读输入带上，为检查一次转移而定位输入字符可能花 $O(n)$ 时间，不能不加条件地把原语写成 $\operatorname{poly}(s)$ 。粗略递推为

T(i)\le C\bigl(2T(i-1)+P(n+s)\bigr),

顶层再至多枚举 $C$ 个接受目标。因为 $b=O(s)$ 、 $C=2^{O(s)}$ ，且 $s\ge\log n$ 给出 $n\le2^{O(s)}$ ，总时间仍至多

C(2C)^{O(b)}\operatorname{poly}(n+s)=2^{O(s^2)}.

这是该模拟算法的上界，不是被判定语言所需时间的下界。取 $s=\log n$ 得 $n^{O(\log n)}$ 时间、 $O(\log^2 n)$ 空间；显式可达性另有多项式时间 BFS，但其队列和访问标记可占多项式空间。两种算法优化的资源不同。

推论与应用

取 $s(n)=\log n$ 得

\mathrm{NL}\subseteq\mathrm{DSPACE}(\log^2 n).

STCON 的 NL 完全性说明有向可达性能够代表所有非确定对数空间计算。本定理以平方对数空间确定化它，却没有把预算压回 $O(\log n)$ ，因而不能解决 L 是否等于 NL。

对于每个固定 $k\ge1$ ，有 $\mathrm{NSPACE}(n^k)\subseteq\mathrm{DSPACE}(n^{2k})$ 。对所有多项式次数取并，并结合确定机器也是非确定机器的特例，便得到

\mathrm{NPSPACE}=\mathrm{PSPACE}.

这里使用的是PSPACE包含所有多项式空间预算，而非某个固定次数在平方后保持不变。结论没有给出多项式时间模拟，也就没有推出 P=NP。完成迁移检验时，可以把预算换为 $s(n)=n^3$ ：确定空间为 $O(n^6)$ ，本模拟的时间上界为 $2^{O(n^6)}$ ；“仍是多项式空间”与“仍是多项式时间”必须分开判断。

参考资料

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, 作者站点 January 2007 草稿，§4.1 与 Remark 4.2（PDF 第 92 页，正文页 76）、§4.3.1 与 Theorem 4.12（PDF 第 98 页，正文页 82）。PDF 页序从封面起计，正文页码指该草稿的印刷页码。
Rafael Oliveira, CS 860, Fall 2022, Lecture 3，slides 25–35，空间条件、中点递归与空间递推；本页使用允许零长路径的“至多”长度口径。
Walter J. Savitch, “Relationships Between Nondeterministic and Deterministic Tape Complexities,” Journal of Computer and System Sciences 4(2), 1970, pp. 177–192，原始论文书目信息；上述证明与页码定位依据前两项公开教学材料。

形式陈述 ​

从工作空间得到有限配置图 ​

递归式为什么正确 ​

八顶点图：失败中点也必须检查 ​

四帧账本与复用时刻 ​

删除一条边后的否实例 ​

时间上界与模型条件 ​

反向链接