Savitch 1970：非确定性空间怎样被确定性平方空间模拟

破除误解：平方模拟不是 P 对 NP，也不是已经关掉 NL 对 L#

第一层误解把标题听成「非确定性与确定性一样强」，或听成萨维奇已经解决了 $P$ 对 $NP$。原文问的不是多项式时间，而是磁带。非确定性机器每一步可以有有限多种合法动作；接受意味着存在一条有限步的转移序列走进接受态，并且整段计算里工作带扫过的格子不超过 $L(n)$。确定性模拟器必须自己找出这条路径是否存在，但不被允许把指数多条路径同时摊在带子上。平方出现在空间上，不出现在「因此 SAT 可在多项式时间判定」。库克问的是多项式时钟，萨维奇问的是工作带格子；两个问题可以在同一台图灵机上陈述，答案彼此不蕴含。把 1970 年收进 1971 年的完全性，会把一次磁带模拟说成一次公式编译。

第二层误解把「平方空间」听成「因此变快了」，或听成已经给出可在二次空间里跑完的实用手续。格局的数目大约是 $2^{O(L(n))}$。朴素的广度优先会把指数多个格局存进工作带，空间跟着指数走。萨维奇把「能否在 $2^m$ 步内从格局 $I$ 走到 $I'$」拆成对中间格局的两次半程询问，两次询问先后使用同一段寄存器。空间降到约 $[L(n)]^2$，时间却可以涨到双重指数量级，因为每一层都要枚举全部合法中间格局。工作带的复用才是二次的来源：递归的两半不是两份并排的带子，而是同一段格子先算左边、擦掉、再算右边。若两半同时留下，空间会随深度指数膨胀，平方立刻作废。定理的几何因此是深度优先的，不是把格局图整张展开。把二次模拟听成工程加速，或把递归听成「每层复制一份图」，会把一条存在性模拟收成操作单，也会把 $O(L^2)$ 读回指数。

第三层误解把 $\mathrm{NL}\subseteq\mathrm{L}$ 写成 1970 年已经关掉的命题。对数空间的非确定性类 $\mathrm{NL}=\mathrm{NSPACE}(\log n)$，确定性类 $\mathrm{L}=\mathrm{DSPACE}(\log n)$。定理只给出 $\mathrm{NL}\subseteq\mathrm{DSPACE}(\log^2 n)$。中间那一档平方对数，既没有把 $\mathrm{NL}$ 推进 $\mathrm{L}$，也没有把它们分开。线性有界自动机的确定与非确定是否等价，也就是 $\mathrm{NSPACE}(n)$ 是否等于 $\mathrm{DSPACE}(n)$，同样仍开放。萨维奇证明的是上下文有关语言可在确定性 $n^2$ 空间内识别，不是确定型线性有界自动机已经够用。把「平方」听成「相等」，会把一条包含写成一条坍缩。

第四层误解把后年的补运算封闭提前写进这一卷，或把格局图上的递归可达听成电路下界。1987 至 1988 年，尼尔·伊默尔曼（Neil Immerman）与罗贝尔特·塞莱普切尼（Róbert Szelepcsényi）各自证明：对 $s(n)\ge\log n$，$\mathrm{NSPACE}(s(n))$ 在补运算下封闭。那是「不存在接受计算」也可以用非确定性对数以上空间来验证，不是「非确定性空间可被确定性平方空间模拟」。两者共享格局计数，问题不同。电路复杂度与 PCP 也不在这十六页里。本页停在磁带模拟的证据对象，不把递归对半写成攻击步骤。

格局图、递归对半，以及 $s(n)\ge\log n$#

装置从瞬时描述开始。机器带一条只读输入带（两端有端符）和有限多条读写工作带。一个瞬时描述记下输入头位置、有限控制器状态，以及每条工作带的内容与磁头位置。萨维奇称之为 ID。因为工作带非空白部分至多 $L(n)$ 格，每个 ID 的长度不超过 $cL(n)$，其中 $c$ 只依赖于那台非确定性机器。ID 数目因此至多指数于 $L(n)$。若输入被接受，则存在一条至多 $2^{c'L(n)}$ 步的接受计算：再长就会重复某个 ID，可以剪掉循环。一步转移给出 ID 之间的有向边。后来教材把这张有向图叫做格局图。图本身不必画在带子上；模拟器只需要能判断两个字符串是否构成一步合法转移。

可达性问的是：起始 ID 能否走到某个接受 ID。把整段路径存下来会再次占用指数空间。关键观察是对半。要判定「从 $I$ 到 $I'$ 至多 $2^m$ 步」，枚举每一个长度不超过 $cL(n)$ 的候选中点 $I''$，先问左半段能否在 $2^{m-1}$ 步内从 $I$ 走到 $I''$，再问右半段能否从 $I''$ 走到 $I'$。左半段一旦得到否定或走完，那段寄存器立刻清掉，留给右半段用。递归深度是 $m$，而 $m$ 取 $O(L(n))$ 已覆盖全部短于指数的路径。每一层只额外保存一个 ID。深度乘以 ID 长度，工作带用量是 $O(L(n)^2)$。平方来自「层数乘格子」，不是来自把图平方。原文把同一件事写成 $r+1$ 个寄存器加同样多枚标签：标签为 1 表示从起点到该寄存器里的 ID 已被核过；算法按 $m$ 进制枚举候选 ID，回溯时清掉较浅的寄存器。教科书里的 $\mathrm{CANYIELD}$ 是这套寄存器的递归写法，不是另一条定理。本页给出的是模拟存在且空间二次，不是把寄存器编排写成装配说明书。

「模拟」在本页里是语言上的：确定性机器接受的集合与非确定性机器相同，并且工作带平方。它不是逐步锁步地重放每一次非确定性选择，也不是把选择写进一条辅助日志。选择被收进「是否存在中点」的枚举。枚举可以按字典序走过全部短字符串，绝大多数根本不是合法 ID，测试一步转移时即失败。合法路径若存在，某次中点组合会把它对半对齐；不存在则全部组合都失败，机器拒绝。这是存在性量词被确定性空间买下来的账，不是一份如何实现非确定性硬件的图纸，也不是一份攻击步骤。

$L(n)\ge\log_2 n$ 不是装饰。ID 必须写下输入头停在第几格。格子编号是 $n$ 的对数，用二进制或原文的二进制变体（dyadic）书写。若允许的工作带短于这段编号，ID 本身就写不下，格局图的顶点集合没有一致的短编码。对数下限因此是编码条件，不是经验阈值。函数还须可测量：存在一台单工作带机器，对长度为 $n$ 的输入恰好扫过 $L(n)$ 格后停机。后来的用语是磁带可构造。没有这条，确定性模拟器无法预先把带子划成等长寄存器。萨维奇写明：常见的 $n$ 与 $\log n$ 的多项式都可测量。常数因子被有限工作带字母表吸收，故 $L(n)$ 与 $\varepsilon L(n)$ 视为同一增长。

刘易斯、斯特恩斯与哈特马尼斯 1965 年已用相近的对半手续证明：上下文无关语言可在确定性 $(\log n)^2$ 空间内识别。萨维奇把同一几何从文法分析搬到任意非确定性带界计算。证明还带出一条较细的推论：若某个上下文有关语言被非确定型线性有界自动机接受，且接受计算的步数是输入长度的多项式，则确定性模拟不必付满 $n^2$——对半深度随多项式时钟取对数，工作带降到约 $n\log^2 n$。多项式时间在这里只缩短需要检查的路径，从而少划几层寄存器；它并不把该语言放进 $P$。

论文还形式化了迷宫：非确定性计算对应于在迷宫里穿线。可穿线迷宫的编码构成一个具体集合，可被非确定性机器在对数空间内接受；若该集合也能被确定性对数空间接受，则对一切 $L(n)\ge\log n$，非确定性与确定性带界类重合。这不是在开一份完全性清单，而是指出：若两类磁带有任何差别，差别已经浓缩在这一种可达性里。后年把有向 $s$-$t$ 连通写成 $\mathrm{NL}$ 完全，形状从这里长出，定义口径是后话。本页不把迷宫改写成寻路手册。

它证明了什么，没有覆盖什么#

它证明了：在可测量且不低于对数的磁带函数上，非确定性 $L(n)$ 空间可被确定性 $[L(n)]^2$ 空间模拟。上下文有关语言因此落入确定性二次空间。把多项式并起来，得到一条立刻改写教科书的推论：$\mathrm{PSPACE}=\mathrm{NPSPACE}$。具体写就是：每个 $k$，非确定性 $n^k$ 空间被确定性 $n^{2k}$ 空间吞掉，而 $n^{2k}$ 仍是多项式；反向包含由确定性机器本就是非确定性机器的特例给出。多项式这一档因此对空间闭合。时间类没有平行的句子：$NP$ 是否等于 $P$，询问机与多一完全性都回答不了，萨维奇的磁带手续也回答不了。空间之所以被平方压回同一多项式档，是因为格局图的直径是指数、对半的深度是线性、每层只存一个短 ID；时间没有同样的「用完即还」的账本。

它没有证明 $\mathrm{NL}=\mathrm{L}$，也没有证明确定型与非确定型线性有界自动机等价。论文开篇把后者写成形式语言里的著名开放问题，给出的是 $n^2$ 上界，不是坍缩。平方留下空隙：$\mathrm{NL}$ 被放进 $\mathrm{DSPACE}(\log^2 n)$，仍可能严格大于 $\mathrm{L}$；$\mathrm{NSPACE}(n)$ 被放进 $\mathrm{DSPACE}(n^2)$，仍可能严格大于 $\mathrm{DSPACE}(n)$。空隙是否为空，1970 年没有裁决，今天也没有。它也没有证明 $\mathrm{NSPACE}(s)=\mathrm{coNSPACE}(s)$。补运算封闭是伊默尔曼–塞莱普切尼的后话，对象是「不存在路径」能否仍用非确定性空间验证。萨维奇验证的是「存在路径」，方法是确定性的递归对半。把补封闭读回 1970 年，会把一次模拟收成一次计数。

它还证明了一种抬升。若对「小」的磁带函数，非确定性与确定性带界类已经重合，则对更大的可测量函数也重合。大输入可以被填充、重新编码，使真正的工作发生在对数尺度的芯上；芯上的等式沿填充手续传回大尺度。因此 $\mathrm{NL}=\mathrm{L}$ 一旦成立，线性有界自动机的确定与非确定之别也会一起倒下。萨维奇把差别浓缩到对数空间的可达性，不是为了宣布差别不存在，而是为了说明：要找缝，先看迷宫。这条抬升仍是条件句，不是分离。

它没有覆盖库克的 SAT，也没有覆盖卡普的二十一题。导师两年后问的是多项式时间里哪一个公式问题完全；学生一年前问的是磁带上确定性要付多少平方代价。完全性是归约闭包；模拟是包含。箭头方向相反：完全性说「若汇点容易则源点容易」，萨维奇说「非确定性空间的语言已经落在确定性平方空间里」，无需再经过一次实例翻译。电路下界、相对化障碍与 PCP 都不在这十六页里。稳健性来自格局的短编码与工作带的复用，不来自后来的求解器或硬件事务内存。概念证据到此为止。寄存器回答的是「二次空间从哪一层账里长出来」；迷宫回答的是「若磁带两类有缝，缝可以钉在一种可达性上」。两句都不是操作单。

跨域连接#

• 计算复杂性：总览页把时间类与空间类画在同一张地图上；$P$ 对 $NP$ 仍开放，$\mathrm{PSPACE}=\mathrm{NPSPACE}$ 却已经写进地图，钉子就是本页的二次模拟。地图可以后写；钉子的金属成分以 1970 年的磁带函数为准。把总览里的「空间也有完全性」提前读成本页，会把一次无条件包含收成后来的 PSPACE 完全问题清单。本页只提供包含，不提供完全性度数。
• 库克一九七一年论文：萨维奇的伯克利导师两年后把非确定性时间编译成公式；学生一年前把非确定性空间压进确定性平方磁带。同一师门，资源不同。库克要的是询问机度数上的完全钉子，萨维奇要的是工作带复用上的包含。把 SAT 的窗口编码听成格局图的对半，会把时间表上的局部子句收成磁带上的中点枚举。两页必须叠着读，才能看见：完全性与模拟不是同一句话的两个年份。
• 卡普一九七二年论文：多一箭头把团、覆盖、回路接到 SAT，问的是「哪些判定问题与可满足性同生共死」。萨维奇没有画出这样的图。他给出的手续对每一个非确定性带界机器各自成立，并不经过一次实例改写。若将来某个 PSPACE 完全问题掉进 $P$，那是时间地图上的坍缩；本页的平方包含是无条件的，不依赖任何完全问题是否属于 $P$。把二十一题听成萨维奇的应用清单，会把空间模拟收成组合归约。
• 可计算性：停机问题把「有没有手续」写成不可判定；本页假定手续存在，并且工作带有界。非确定性空间里的语言都可判定，萨维奇还给出确定性二次空间的手续。可判定与多项式时间可判定是两层边界，可判定与对数空间可判定又是一层。把可达性听成停机，会把资源问题收成存在问题。对角化在无界时间里分开递归与递归可枚举；在带对数以上磁带时钟的世界里，萨维奇表明非确定性并不自动换来更多空间档。
• 自动机与形式语言：上下文有关语言对应非确定型线性有界自动机。萨维奇开篇就写这个问题：有没有一个上下文有关语言，确定型线性有界自动机认不出来？他证明每个这样的语言都落在确定性 $n^2$ 空间，于是「线性」被换成「二次」，问题本身仍开放。黑田成幸 1964 年留下的确定与非确定 LBA 之别，没有被平方模拟取消。迷宫穿线则把自动机的一步转移写成图上的边，并不把自动机课收成寻路实验。
• 证明：递归对半是一份关于「存在路径」的证明方案：把长计算拆成两段短计算，直到一步转移可用查表核完。证书不是那条路径本身——路径可能指数长，存不下——而是这棵对半树在工作带上的遍历记录，同一段带子被反复覆盖。数学里的普遍证明要求从公理推出必然；这里的必然相对于那台非确定性机器的转移表。验证的是存在性，不是「所有路径都接受」。把二次空间听成已经给出一条可展示的接受路径，会把模拟器的复用账本说成一份欧几里得式的构造。

参考文献#

• Walter J. Savitch, "Relationships Between Nondeterministic and Deterministic Tape Complexities", Journal of Computer and System Sciences 4(2), 1970, pp. 177–192. DOI: 10.1016/S0022-0000(70)80006-X. —— 本文对象：可测量磁带上的二次确定性模拟、上下文有关语言的 $n^2$ 空间，以及可穿线迷宫。
• Walter J. Savitch, "Deterministic Simulation of Non-deterministic Turing Machines (Detailed Abstract)", Proceedings of the 1st Annual ACM Symposium on Theory of Computing, Marina del Rey, 1969, pp. 247–248. DOI: 10.1145/800169.805439. —— 论文脚注所称的预先宣布。
• P. M. Lewis II, R. E. Stearns & J. Hartmanis, "Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages", 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 191–202. DOI: 10.1109/FOCS.1965.14. —— 上下文无关语言的 $(\log n)^2$ 确定性空间，论文点明的相近手续。
• S.-Y. Kuroda, "Classes of Languages and Linear-Bounded Automata", Information and Control 7(2), 1964, pp. 207–223. DOI: 10.1016/S0019-9958(64)90120-2. —— 上下文有关语言与线性有界自动机，论文开篇所推广的开放问题。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 用以标明时间完全性不是 1970 年的对象。
• Neil Immerman, "Nondeterministic Space Is Closed Under Complementation", SIAM Journal on Computing 17(5), 1988, pp. 935–938. DOI: 10.1137/0217058. —— 后年的补运算封闭，用以标明 $\mathrm{NL}=\mathrm{coNL}$ 不是本页封面。
• John E. Hopcroft & Jeffrey D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969. —— 论文所引的多带机器与磁带压缩传统。

延伸阅读#

• 与 计算复杂性 对读：先看空间类在地图上的位置，再看本页如何把 $\mathrm{NPSPACE}$ 压回 $\mathrm{PSPACE}$。
• 与 库克一九七一年论文 对读：同一师门，一年问磁带平方，两年后问时间完全。
• 与 卡普一九七二年论文 对读：多一完全性与无条件空间包含不是同一类箭头。
• 与 可计算性 对读：可判定并不给出对数空间；萨维奇给出的是二次确定性空间。
• 与 自动机与形式语言 对读：LBA 问题仍开放，二次空间只改上界。
• 与 P vs NP 的证明障碍 对读：空间被平方压回同一多项式档，时间没有平行句子。