Immerman–Szelepcsényi 1988：非确定性空间怎样对补运算封闭

破除误解：补封闭不是 P 对 NP，也不是已经关掉 NL 对 L#

第一层误解把标题听成「非确定性与确定性一样强」，或听成已经解决了 $P$ 对 $NP$。原文写的是补运算，不是确定性模拟。一台非确定性 $s(n)$ 空间机器接受，当且仅当存在一条工作带不超过 $s(n)$ 的计算走进接受态。补语言要的是：所有合法计算都不接受。时间类里，这个「所有」把 $NP$ 送到 $\mathrm{coNP}$，$NP=\mathrm{coNP}$ 至今开放。空间类里，伊默尔曼证明「所有」可以改写成一次普查：可达格局的个数是 $O(s(n))$ 比特的整数，恰好写得进同一档工作带。平方出现在萨维奇的磁带复用上，不出现在本页。把 1988 年收进 1971 年的完全性，会把一次计数说成一次公式编译；把 1988 年收进 1970 年的平方，会把一次补验证说成一次确定性模拟。

第二层误解把「归纳计数」听成已经给出可在车间里跑完的普查算法，或听成必须把格局图整张画在带子上。引理依赖非确定性猜测：对每一个字典序目标串，机器要么猜出一条从起点到它的路径并给计数器加一，要么跳过它。猜错的分支自行死掉；正确的分支会碰到全部可达者，一个不漏、一个不多。图本身不必存下来。模拟器只保存当前目标、当前计数、以及一条正在核验的短路径。把计数听成广度优先的队列，会把 $O(s(n))$ 空间读回指数；把猜测听成随机采样，会把存在性量词收成蒙特卡洛。本页给出的是非确定性空间里的存在性手续，不是一份操作单。

第三层误解把 $\mathrm{NL}=\mathrm{L}$ 写成 1988 年已经关掉的命题，或把上下文有关语言的补封闭听成确定型与非确定型线性有界自动机已经等价。对数空间的非确定性类 $\mathrm{NL}=\mathrm{NSPACE}(\log n)$，确定性类 $\mathrm{L}=\mathrm{DSPACE}(\log n)$。定理给出 $\mathrm{NL}=\mathrm{coNL}$，再与萨维奇合写，只得到 $\mathrm{NL}\subseteq\mathrm{DSPACE}(\log^2 n)$。中间那一档平方对数仍在。黑田成幸 1964 年留下两个线性有界自动机问题：确定与非确定是否等价；上下文有关语言是否对补封闭。他证明若第二问为否，则第一问亦否。本页把第二问改成是，第一问的否向蕴含因此失效，问题本身仍开放。把「补封闭」听成「确定化」，会把一条类等式收成一条坍缩。

第四层误解把两篇 1988 年论文焊成一套装置，或把后年的 PCP、电路下界提前写进这四页。伊默尔曼的路线从一阶归纳定义与带正传递闭包的一阶逻辑走来：他已证明 $\mathrm{NL}$ 等于 $\mathrm{FO}(\mathrm{pos}\,\mathrm{TC})$，再证明这个类对补封闭，然后在 SIAM 文本里改用机器语言重写。塞莱普切尼的路线从非确定性自动机的强迫枚举走来，直接瞄准上下文有关语言。哥德尔奖把两次独立证明并列，不是把两套循环收成一个伪代码。本页以 SIAM 的两条引理为封面装置，以《Acta Informatica》为独立邻居。

归纳计数、强迫枚举，以及 $s(n)\ge\log n$#

装置从格局开始。一台非确定性 $s(n)$ 空间机器带着一条只读输入带和有限多条工作带。一个格局记下有限控制器状态、输入头位置、各工作带内容与磁头位置。因为工作带非空白部分至多 $s(n)$ 格，格局可以写成长度 $O(s(n))$ 的串。$s(n)\ge\log n$ 不是装饰：输入头停在第几格，编号要 $\log n$ 比特。若允许的工作带短于这段编号，顶点集合没有一致的短编码，普查函数也写不下。格局数目至多 $c^{s(n)}$，因此可达者的个数 $N$ 是一个 $O(s(n))$ 比特的整数，恰好放得进同一档空间。一步转移给出有向边。图不必画出来；机器只需要判断两个短串是否构成一步合法转移。

伊默尔曼把定理拆成两条引理。第一条假定 $N$ 已知。从字典序最小的长度为 $O(s(n))$ 的候选串扫到最大。对每一个目标，非确定性机器要么猜一条从起始格局出发、长度不超过格局总数的路径并核验每一步，猜中则计数器加一；要么放弃这个目标，只把字典序推进一格。若某个已被走到的目标是接受格局，这条分支拒绝。扫完之后，若计数器恰好等于 $N$ 且从未碰到接受格局，则接受。语义是：接受当且仅当机器找到了全部 $N$ 个可达格局，并且其中没有接受者。若原机器接受，可达格局里至少有一个接受者，非接受的可达者至多 $N-1$ 个，任何分支都凑不满 $N$。若原机器拒绝，全部 $N$ 个可达者都不接受，存在一条猜测序列把它们逐个找齐。补语言因此落在 $\mathrm{NSPACE}(s(n))$。

第二条引理计算 $N$。令 $N_d$ 为至多 $d$ 步可达的格局数。$N_0$ 是起始格局这一处。归纳步骤假定 $N_d$ 已知，要得到 $N_{d+1}$。仍按字典序扫描每一个目标。对每个目标，机器必须再次走访全部 $N_d$ 个至多 $d$ 步可达的格局：对每一个，猜一条短路径；若找不齐这 $N_d$ 个，分支拒绝。找到之后，检查目标是否等于其中某一个，或是否由其中某一个一步可达。是则给 $N_{d+1}$ 的计数器加一，并换下一个目标；否则不加。扫完所有目标，计数器里就是 $N_{d+1}$。因为格局图的直径小于 $c^{s(n)}$，$N$ 等于第一个满足 $N_d=N_{d+1}$ 的值。伊默尔曼写明：标准定义里，非确定性空间 $s(n)$ 意味着没有任何一条选择序列会扫过超过 $s(n)$ 格，因此 $s$ 不必事先磁带可构造；工作带按需要增长即可。线性带压缩把构造的常数因子吃掉，他估计实际乘数大约是八。

「模拟」在本页里是语言上的：存在一台非确定性 $s(n)$ 空间机器，接受的集合恰好是原语言的补。不存在被收进「普查对得上、且接受格局一次都没出现」。枚举按字典序走过全部短字符串，绝大多数根本不是合法格局，测试一步转移时即失败。这是全称量词被非确定性空间买下来的账，不是一份攻击步骤。

塞莱普切尼的强迫枚举是另一条独立的路，不要把上面的 $N_d$ 循环写进他的标题。他的对象首先是非确定性自动机：要识别补语言，就强迫机器按一种固定顺序把所有可达格局点名一遍；点名失败的分支作废，点名成功且其中无接受者则承认输入在补里。语境是线性有界自动机与上下文有关语言，不是一阶传递闭包。两条路在格局普查上相遇，装置、刊物、作者身份都不相同。把《Acta Informatica》的六页收进 SIAM 的两条引理，会把一次独立发现说成一次改写。本页叠着读，是为了标明共同定理；封面仍停在耶鲁那四页。

推论立刻改写教科书。黑田已证明上下文有关语言等于 $\mathrm{NSPACE}(n)$，补封闭因此落到这一族语言上，第二 LBA 问题闭合。对数空间的交替层次与神谕层次随之塌到 $\mathrm{NL}$：伊默尔曼此前已把 $\mathrm{NL}$ 写成 $\mathrm{FO}(\mathrm{pos}\,\mathrm{TC})$，补封闭让正传递闭包与可任意放置否定的传递闭包重合。迈克尔·费希尔观察到，有了补就可以对非确定性空间做对角化，从而给出比旧证明干净得多的紧层次：对磁带可构造的 $s(n)\ge\log n$，若 $t(n)/s(n)\to 0$，则 $\mathrm{NSPACE}(t(n))\ne\mathrm{NSPACE}(s(n))$。层次能收紧，是因为补让对角化机器知道何时翻转；这不是哈特马尼斯–斯特恩斯那条确定性时间层次的翻版，时钟与资源都不同。同卷前后，博罗丁、库克、戴蒙德、鲁佐与汤帕把归纳计数推到 $\mathrm{LOGCFL}$ 的补封闭，以及对称对数空间落入无误差概率对数空间。那些是后续，不是这四页的封面。

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

它证明了：在不低于对数的空间界上，非确定性空间类等于自己的补类。$\mathrm{NL}=\mathrm{coNL}$。上下文有关语言对补封闭。对数空间的交替层次与神谕层次塌到 $\mathrm{NL}$。带正传递闭包的一阶逻辑因此可以对否定封闭。非确定性空间的层次可以写成几乎紧的真包含。把多项式并起来，得到 $\mathrm{NPSPACE}=\mathrm{coNPSPACE}$；再与萨维奇的平方合写，$\mathrm{PSPACE}$ 对补也早已封闭，本页提供的是非确定性这一侧自己的闭合，不必先付一次平方。稳健性来自格局的短编码：普查整数与当前目标都是 $O(s(n))$ 长，猜测路径可以逐格覆盖。时间可以涨到与格局数目同阶，空间账本不涨。

它没有证明 $\mathrm{NL}=\mathrm{L}$，也没有证明确定型与非确定型线性有界自动机等价。补封闭取消了黑田那条「若补不封闭则两类 LBA 分离」的否向蕴含，没有给出正面向的坍缩。萨维奇留下的平方空隙仍在：$\mathrm{NL}$ 被放进 $\mathrm{DSPACE}(\log^2 n)$，仍可能严格大于 $\mathrm{L}$；$\mathrm{NSPACE}(n)$ 被放进 $\mathrm{DSPACE}(n^2)$，仍可能严格大于 $\mathrm{DSPACE}(n)$。空隙是否为空，1988 年没有裁决，今天也没有。伊默尔曼文末把「萨维奇定理是否最优」与「非确定性空间是否等于确定性空间」并列写成仍然开放。把补封闭读回 1970 年，或把 1970 年的平方读成本页已经消掉，都会把一次计数收成一次模拟。

它没有证明 $NP=\mathrm{coNP}$。多项式时间里，一张计算表的尺寸是输入的多项式，可能的表却有指数多张。普查函数的比特数虽是多项式，要把指数多个候选走访一遍，时间会超出 $NP$ 的时钟。空间之所以能买下全称量词，是因为可达格局只有 $2^{O(s)}$ 个、计数器只有 $O(s)$ 比特，而 $\mathrm{NL}$ 机器被允许用与格局数目同阶的时间去点名。时间没有同样的「用完即还」的短账本。库克的完全性把存在性量词钉在 SAT 上；本页把全称量词留在空间里。箭头方向不同：完全性说「若汇点容易则源点容易」；补封闭说「拒绝与接受占用同一档非确定性空间」。相对化障碍、自然证明与 PCP 都不在这四页里。

它没有覆盖萨维奇的二次模拟，也没有把两篇 1988 年论文焊成一份伪代码。萨维奇验证存在路径，付确定性平方；本页验证不存在接受路径，付非确定性普查；塞莱普切尼验证同一句结论，装置另起一行。把三句话收成「1980 年代的空间定理」，会把磁带复用、普查与自动机点名说成同一个因子。概念证据到此为止。普查回答的是「全称量词凭什么写得进 $O(s)$ 格」；对数下限回答的是「格局编码与计数器凭什么同时放得下」。两句都不是操作单。

跨域连接#

• 萨维奇一九七〇年论文：邻居是平方模拟，封面不是。萨维奇用递归对半把存在路径压进确定性 $s^2$ 磁带；本页用归纳计数把不存在接受路径留在非确定性 $s$ 磁带。格局图共用，账本相反：一个付平方换确定性，一个不付平方却仍要非确定性猜测。合写只得到 $\mathrm{NL}\subseteq\mathrm{DSPACE}(\log^2 n)$，并不给出 $\mathrm{NL}=\mathrm{L}$。把 1970 年听成本页的引理零，会把一次包含收成一次补封闭。
• 计算复杂性：总览页把 $\mathrm{NL}=\mathrm{coNL}$ 画进空间地图，并把 $\mathrm{PSPACE}$ 对补封闭写成已钉死的一格。钉子的金属成分以 1988 年的普查为准，不是后来的完全问题清单。地图可以后写；本页只提供非确定性空间自己吞下补运算的那一次手续。把总览里的「空间也有完全性」提前读成本页，会把一次类等式收成有向可达性的 $\mathrm{NL}$ 完全度数。
• 库克一九七一年论文：库克把非确定性时间的存在性量词编译成可满足性；本页把非确定性空间的全称量词改写成普查。同一句「非确定性」，资源不同。SAT 完全并不迫使 $NP=\mathrm{coNP}$；$\mathrm{NL}$ 完全的有向可达性却因为本页而与其补同在 $\mathrm{NL}$。把窗口编码听成字典序点名，会把时间表上的局部子句收成空间上的计数器。
• 哈特马尼斯–斯特恩斯一九六五年论文：那一卷用实时可数时钟在确定性时间上对角化，空隙来自多带到单带的平方模拟。本页让非确定性空间也可以对角化，空隙收成 $t/s\to 0$，因为补封闭提供了翻转所需的另一侧语言。两个层次不是同一个钟。把 1965 年的 $T^2/U$ 条件读进 $\mathrm{NSPACE}$，会把带压缩的时间账写成格局普查的空间账。
• 可计算性：递归可枚举集对补不封闭，停机问题的补不可递归可枚举。本页假定手续存在并且工作带有界，证明有界非确定性空间与其补重合。可判定与对数空间可判定是两层边界；可枚举与补可枚举又是一层。把 $\mathrm{NL}=\mathrm{coNL}$ 听成递归与递归可枚举重合，会把资源问题收成存在问题。对角化在无界时间里分开这两类；在对数以上磁带上，普查把那条裂缝填上。
• 自动机与形式语言：上下文有关语言对应非确定型线性有界自动机。黑田的第二问被这四页与《Acta Informatica》那六页同时关掉：这一族语言对补封闭。第一问仍开放。强迫枚举把自动机的可达格局按顺序点名，并不把自动机课收成扫描器实验。乔姆斯基谱系在这一层因此对布尔运算闭合，却仍可能把确定与非确定的线性有界自动机分开。

参考文献#

• Neil Immerman, "Nondeterministic Space is Closed Under Complementation", SIAM Journal on Computing 17(5), 1988, pp. 935–938. DOI: 10.1137/0217058. —— 本文封面：归纳计数、$\mathrm{NSPACE}(s)=\mathrm{coNSPACE}(s)$，以及上下文有关语言的补封闭。
• Neil Immerman, "Nondeterministic Space is Closed Under Complementation", Proceedings of the Third Annual Structure in Complexity Theory Conference, Georgetown University, 1988, pp. 112–115. DOI: 10.1109/SCT.1988.5270. —— 同年六月的会议文本。
• Róbert Szelepcsényi, "The method of forced enumeration for nondeterministic automata", Acta Informatica 26, 1988, pp. 279–284. DOI: 10.1007/BF00299636. —— 独立证明：强迫枚举与上下文有关语言的补。
• Róbert Szelepcsényi, "The method of forcing for nondeterministic automata", Bulletin of the EATCS 33, 1987, pp. 96–100. —— 《Acta Informatica》文本的通报预告。
• 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. —— 两个 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. —— 邻居：确定性平方模拟，不是本页封面。
• Neil Immerman, "Languages that Capture Complexity Classes", SIAM Journal on Computing 16(4), 1987, pp. 760–778. DOI: 10.1137/0216051. —— $\mathrm{NL}=\mathrm{FO}(\mathrm{pos}\,\mathrm{TC})$，SIAM 四页所回收的逻辑前史。
• Juris Hartmanis & H. B. Hunt III, "The LBA Problem", in Richard M. Karp (ed.), Complexity of Computation, SIAM-AMS Proceedings 7, 1974. —— 伊默尔曼开篇所指的问题史。
• 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. —— 用以标明时间完全性不是 1988 年的对象。

延伸阅读#

• 与 萨维奇一九七〇年论文 对读：平方模拟验证存在，归纳计数验证不存在，两页必须分开。
• 与 计算复杂性 对读：先看空间地图上 $\mathrm{NL}=\mathrm{coNL}$ 的位置，再看本页的普查从哪一格钉子长出。
• 与 库克一九七一年论文 对读：时间上的存在性完全钉子，并不给出时间上的补封闭。
• 与 哈特马尼斯–斯特恩斯一九六五年论文 对读：确定性时间层次与非确定性空间层次用的不是同一只钟。
• 与 可计算性 对读：RE 对补不封闭；有界非确定性空间对补封闭。
• 与 自动机与形式语言 对读：上下文有关语言的补已闭合，LBA 确定化仍开放。
• 与 P vs NP 的证明障碍 对读：空间补封闭不迁移到 $NP$ 对 $\mathrm{coNP}$，对角化仍跨不过多项式量词。