STCON 的 NL 完全性

STCON 把非确定对数空间的全部能力浓缩为“有向图中是否存在一条路”，因为非确定性计算本身就是在配置图中选择一条路径。成员性来自只保存当前顶点并逐步猜边；困难性则把任意小空间机器的配置当作图顶点，合法一步当作有向边。对数空间机器只有多项式多个配置，因此这张配置图既是多项式规模，又可由小空间归约隐式生成，一个具体图问题便由此代表整个 NL。

给定图 $s\to a\to t$，NL 机器先猜 $a$ 再猜 $t$ 即有接受分支，只需存当前顶点编号与步数。对语言 $L\in NL$ 的机器 $M$，映射输入 $x$ 到配置图的起始配置 $c_s$、接受配置 $c_t$；$M$ 有接受分支当且仅当 $c_s$ 可达 $c_t$。

STCON 在显式图上可由 BFS 或 DFS 在多项式时间内解决，所以完备性立即给出 $NL\subseteq P$。无向可达性后来被证明属于 L，但这不自动把有向 STCON 降到 L；$L=NL$ 仍未知。完全性通常相对于 logspace many-one 归约：若改用过强的多项式时间归约，归约器本身已能解决 STCON，会削弱“NL 中最难”的分辨力。

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

有向图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。 可达性给出 NL公理库复杂度类 NLComplexity class NL · Nondeterministic logspace可在非确定性对数空间内判定的语言类。 的标准完全问题，并自然处于 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 中。Immerman–Szelepcsényi 定理公理库Immerman–Szelepcsényi 定理Immerman–Szelepcsényi theorem · NL equals coNL非确定性空间类在补运算下封闭，特别地 NL 等于 coNL。 给出 $\mathrm{NL}=\mathrm{coNL}$，可视为“不可达也能在非确定对数空间验证”，Savitch 定理则用递归中点把 STCON 确定化到 $O({\log }^{2}n)$ 空间。