形式陈述

有向 $s$–$t$ 可达性问题

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

在确定性对数空间多一归约下是 NL 完全的。成员关系可由 NL 机器保存当前顶点与至多 $|V|$ 的计数器，并非确定性地猜测下一条边。对任意 $A\in \mathrm{NL}$，给定判定 $A$ 的机器 $M$ 与输入 $x$，可在对数空间内逐位生成 $M(x)$ 的配置图；于是

$$x\in A⟺C_{\mathrm{start}}⇝C_{\mathrm{accept}}.$$

直觉

非确定性计算本身就是在配置图中选择一条路径。对数空间配置只有多项式多个，因此这张隐式图仍可作为多项式规模的归约输出；一个具体图问题便代表了整个 NL。

例子与边界

STCON 在显式图上可由 BFS 或 DFS 在多项式时间内解决，所以完备性立即给出 $\mathrm{NL}\subseteq \mathrm{P}$。这里的困难性依赖对数空间归约；若只用多项式时间归约，归约器本身已能解决 STCON，无法刻画 NL 内部的精细结构。无向可达性属于 L，不能据此把有向 STCON 也放入 L，除非进一步证明 $\mathrm{L}=\mathrm{NL}$。

推论与应用

要证明一个问题 NL 困难，只需从 STCON 做对数空间归约；要证明 NL 的闭包或模拟结论，也常可先在配置图可达性上完成。它是低空间复杂性中对应 SAT 的标准完备问题。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 8。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 4。