STCON 的 NL 完全性

形式陈述 ​

有向图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。的源点到目标点可达性语言为

$$\mathrm{STCON}=\{⟨G,s,t⟩:G\text{ 中存在从 }s\text{ 到 }t\text{ 的有向路径}\}.$$

允许零长度路径，所以合法实例中 $s=t$ 时答案为是。本页也允许自环，即弧集可为 $V\times V$ 的任意子集，邻接矩阵的对角位可以为 $1$。固定一种显式编码：顶点编号为 $0,\dots ,N-1$，$N\ge 1$；字符串依次写顶点数 $N$、按行排列的 $N^2$ 个邻接矩阵位、源点 $s$、目标点 $t$，四个字段用分隔符连接，三个整数均用无多余前导零的二进制表示。矩阵尺寸、符号或编号不合法的字符串不属于该语言。STCON 在确定性对数空间多一归约下是 NL公理库复杂度类 NLComplexity class NL · Nondeterministic logspace可在非确定性对数空间内判定的语言类。 完全的，也就是 STCON 属于非确定对数空间类，且每个 $A\in \mathrm{NL}$ 都有 $A{\le }_m^{\mathrm{L}}\mathrm{STCON}$。

这里 $A{\le }_m^{\mathrm{L}}B$ 表示存在总函数 $f$，由总停机的确定性转换器在输入长度 $n$ 的 $O(\log n)$ 工作空间内输出，且对所有字符串 $x$ 都满足

$$x\in A⟺f(x)\in B.$$

转换器有只读输入带和只写、不可回读的输出带；输出长度为多项式。标准模型也能从停机和多项式多个内部配置推出这一长度界：若不含输出位置的内部配置重复，机器因无法读输出而会重复同一行为，不能最终停机。归约只负责构造实例，不调用目标语言判定器。

成员性：有界猜路 ​

NL 机器先用计数器检查编码合法性：扫描取得输入长度 $\ell$，读取顶点数字段时一旦数值超过 $\ell$ 就拒绝，因为合法输入仅矩阵就有 $N^2$ 位。这样即使遇到非法的超长数字，也不必保存超过 $O(\log \ell )$ 位的整数；其余字段和矩阵尺寸可用同阶空间计数核对。然后保存当前顶点 $v$ 和步数 $j$，初始为 $v=s,j=0$。若 $v=t$ 则接受；否则，在 $j<N-1$ 时猜测下一个顶点 $w$，扫描只读矩阵检查 $v\to w$，有边才更新当前位置并增加步数。无边、非法编号或用尽预算仍未到达目标的分支拒绝。

若图中可达，去掉回路便得到至多 $N-1$ 步的简单路径，某个分支能够猜中并接受。若不可达，任何由合法边组成的猜测都不会到目标，所有分支最终拒绝。当前位置、候选编号和步数各用 $O(\log N)$ 位，矩阵扫描索引用 $O(\log |x|)$ 位，因此总工作空间为 $O(\log |x|)$。步数上限保证每条分支停机，即使图中有自环也成立。

困难性：逐位生成配置图 ​

任取 $A\in \mathrm{NL}$，固定判定它的对数空间非确定机器 $M$。对于输入 $x$，完整配置包括有限状态、$O(\log n)$ 位工作内容、工作头位置和输入头位置，所以可用 $b=O(\log n)$ 位编码。令 $Q=2^b$，归约器保留编号 $0,\dots ,Q-1$ 的所有候选作为图顶点，另添编号为 $Q$ 的超级接受点 $a_{\ast }$；不合法的候选编码成为孤立点。这样无需先计算“第几个合法配置”，图顶点数 $N=Q+1$ 已经明确且为多项式。

转换器先输出二进制顶点数 $Q+1$ 和分隔符，再按行序枚举 $u=0,\dots ,Q$，每行枚举 $v=0,\dots ,Q$。每对 $(u,v)$ 恰好输出一个矩阵位，规则为：

• 若 $u,v<Q$，两者均为合法配置，且 $M$ 在输入 $x$ 上能够一步从 $u$ 转移到 $v$，输出 $1$。
• 若 $u<Q$、$v=Q$，且 $u$ 是合法接受配置，输出 $1$。
• 其余情况全部输出 $0$，包括超级接受点所在的整行。

因此每行最后一位直接写出该顶点是否连向 $a_{\ast }$，不需要回头补列。合法性检查须确认带符号、状态、工作预算、各头位置和固定填充均有效，一步检查则逐位置比较带内容并核对有限转移规则。需要输入字符时回扫原输入定位。转换器只保存两个编号和少量扫描计数器，整个过程只用 $O(\log n)$ 工作位。

完整矩阵输出结束后，转换器依次输出分隔符、初始配置编号 $c_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$、分隔符和目标编号 $Q$，完成开头约定的四字段编码。初始配置必有合法编码；孤立的非法候选不能制造接受路径。邻接矩阵有 $(Q+1{)}^2$ 位，是多项式长度，所有字段顺序写到输出带，转换器既不保存整张矩阵，也不回读已输出的内容。对于任意字符串 $x$，机器 $M$ 都定义了计算，故此构造是全函数；若 $A$ 的应用语法把某些串定义为非法，$M$ 对它们拒绝，图也随之成为否实例。

若 $x\in A$，取一条接受计算，其配置序列给出从 $c_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ 到某个接受配置的图路径，再走一步就到 $a_{\ast }$。反过来，若图中存在起点到 $a_{\ast }$ 的路径，最后一条边的前驱必是合法接受配置；此前每条边均为 $M(x)$ 的真实一步转移，所以该路径给出接受分支。于是

$$x\in A⟺⟨G_{M,x},c_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x),a_{\ast }⟩\in \mathrm{STCON},$$

因此，归约在两个方向都保持成员资格，完成困难性证明。

直觉

非确定机器每次选择一个后继配置，恰好对应在有向图上选一条出边。对数空间的作用有两层：一份配置足够短，因而所有配置的总数只有多项式；检查两份配置之间是否有一步边也足够省空间，因而整张图能逐位生成。仅证明“图的规模是多项式”还不够，生成它的工作区也必须满足对数预算。

归约器的输出可以比内存大很多，就像用两只计数器依次打印矩阵的每个格子。输出带不可回读，因此已经打印的内容不占工作空间，也不能供后续计算读取。下一节进一步说明，当目标算法想读回这张图时，复合机器怎样重新生成需要的那一位。

例子与边界

同一八点图的两种答案 ​

取顶点 $0,\dots ,7$，边为链 $0\to 1\to 2\to 3\to 4\to 5\to 6$，另有 $0\to 7$ 与 $7\to 7$，询问从 $0$ 到 $6$。猜路分支 $0,1,2,3,4,5,6$ 在六步后接受；猜到 $7$ 的分支即使不断选择自环，也会在七步预算用尽时拒绝。存在拒绝分支不影响是实例的接受，成员性只要求至少一个接受分支。

删除 $4\to 5$ 后，从源点可达集合是 $\{0,1,2,3,4,7\}$。每条合法分支都被困在该集合，因而所有分支拒绝。这与Savitch 定理公理库Savitch 定理Savitch's theorem通过配置可达性的中点递归与工作区复用，把非确定空间 s 确定化为平方空间。中的中点表使用完全相同的图：前者展示非确定地猜一条路，后者展示如何用确定性递归穷尽中点而复用工作区。

低空间复合：把输出作为虚拟输入 ​

设 $f$ 是上面的对数空间转换，输出长度 $m\le n^c$；假设目标语言有一个对数空间判定器 $D$。不能先把 $f(x)$ 全部写入可读工作带，再运行 $D$，因为这一步就可能使用多项式空间。正确模拟只保存 $D$ 的工作区、状态和虚拟输入头位置 $j$，需要读 $f(x)$ 的第 $j$ 位时，从头重跑转换器 $f$。

重跑时另设输出计数器，每当 $f$ 准备写一位就增加计数，计数到 $j$ 时把那一位交给 $D$；之前的输出全部丢弃。如果需要长度或右端标记，则重跑到结束并计数。每次读字符可以重复同样过程，无须缓存已读前缀。$D$ 的工作区用 $O(\log m)$ 位，虚拟输入索引用 $O(\log m)$ 位，转换器及其输出计数器用 $O(\log n)$ 位；由 $m\le n^c$，这些空间相加仍为 $O(\log n)$。

例如虚拟输入是配置图的邻接矩阵，$D$ 想读第 $(u,v)$ 个矩阵位时，复合机按图生成顺序重算到那一位，取得边是否存在的答案，再恢复 $D$ 的执行。若接续的是另一个对数空间转换器，也同样按需模拟它的输入读取，同时将最终输出写到真正的只写输出带。这说明对数空间归约可复合，且目标属于 L 时源也属于 L。

归约方向与资源界 ​

若要证明目标问题 $B$ 为 NL 困难，应构造 $\mathrm{STCON}{\le }_m^{\mathrm{L}}B$；目标算法便能经过转换解决 STCON，再借传递性解决所有 NL 语言。反向 $B{\le }_m^{\mathrm{L}}\mathrm{STCON}$ 只表示可用 STCON 的算法解决 $B$，不证明 $B$ 困难。困难性还必须配合 $B\in \mathrm{NL}$，才能得到完全性。

多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。不足以表达这里的精细困难性。STCON 可用 BFS 在多项式时间内判定；上述配置图也可在多项式时间构造，因此 NL 包含于 P。于是一个多项式时间归约器可以先解决任意 NL 源问题，再按答案输出任意非平凡目标语言中固定的是实例或否实例。这种归约无法辨认对数空间的难度差异。

推论与应用

配置图构造与显式图搜索给出 $\mathrm{NL}\subseteq \mathrm{P}$，但 BFS 的访问标记和队列不保证对数空间。把同一可达性问题交给 Savitch 定理公理库Savitch 定理Savitch's theorem通过配置可达性的中点递归与工作区复用，把非确定空间 s 确定化为平方空间。，则得到确定性 $O({\log }^{2}n)$ 空间算法；这是空间保证，不能把它的中点枚举误记为多项式时间保证。

STCON 属于 L 当且仅当 L=NL：正向由本页的完全性和低空间复合得出，反向因为 STCON 本来就属于 NL。这一等价明确了试图把有向可达性压到对数空间的意义。Immerman–Szelepcsényi 定理公理库Immerman–Szelepcsényi 定理Immerman–Szelepcsényi theorem · NL equals coNL非确定性空间类在补运算下封闭，特别地 NL 等于 coNL。另给出 NL 对补封闭，因此有向不可达性也有非确定对数空间算法；这不是简单交换猜路机器的接受和拒绝状态。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, 作者站点 January 2007 草稿，§4.4、Definition 4.14（PDF 第 100 页，正文页 84）与 Lemma 4.15（PDF 第 100–101 页，正文页 84–85）：对数空间归约和虚拟输入；Theorem 4.16（PDF 第 101–102 页，正文页 85–86）：STCON 的配置图完全性证明。PDF 页序从封面起计。
• Rafael Oliveira, CS 860, Fall 2022, Lecture 3，slides 22–24：对数空间归约与 PATH 完全性。
• Michael Sipser, MIT 18.404J, Fall 2020, Lecture 19，slides 6–8：只读输入、L/NL 与配置计数。