复杂度类 NL

NL 允许对数工作空间中的非确定选择，因此能只记住当前路径而不保存所有已访问顶点，用很少内存“猜”出一条多项式长度的见证路径；存在一条正确猜测路径就足以接受。接受语义是存在某条分支，而不是随机成功，工作空间小也不限制总分支数。与时间复杂度不同，非确定空间可以通过递归可达性模拟为平方级确定空间，且 NL 对补封闭，这两点体现了空间可反复利用的特殊结构。

有向图可达性中，机器只需保存当前顶点和至多 $n$ 步的计数器，每步非确定猜下一邻点；若存在 $s$ 到 $t$ 的路径，就存在长度至多 $n-1$ 的简单路和相应接受分支，故 STCON 属于 NL。计数器也保证每条分支多项式时间停机，不能让“猜一条路径”无限走而不受控。若用确定性 BFS 保存整个 frontier 与 visited 集，通常需要线性空间，不能直接得到 L 上界。

$\mathrm{L}\subseteq \mathrm{NL}$ 显然，但是否严格包含未知。Immerman–Szelepcsényi 定理给出 $\mathrm{NL}=\mathrm{coNL}$；该结论不能从“交换接受和拒绝状态”直接得到，因为非确定性采用存在分支语义。把非确定分支视为概率分支同样会改变类：NL 只关心是否存在，而不关心接受分支比例。

NL 完全性把低空间图问题集中到可达性。Savitch 定理给 $\mathrm{NL}\subseteq \mathrm{DSPACE}({\log }^{2}n)$，而补闭包定理使“不可达”同样可在非确定性对数空间判定。

STCON 的 NL 完全性公理库STCON 的 NL 完全性NL-completeness of STCON · Directed reachability is NL-complete有向图可达性在确定性对数空间多一归约下是 NL 完全问题。 使有向可达性成为该类的标准代表。Immerman–Szelepcsényi 定理公理库Immerman–Szelepcsényi 定理Immerman–Szelepcsényi theorem · NL equals coNL非确定性空间类在补运算下封闭，特别地 NL 等于 coNL。 给出 $NL=coNL$，Savitch 定理公理库Savitch 定理Savitch's theorem对适当空间函数 s，NSPACE(s) 包含于 DSPACE(s²)。 则推出 $NL\subseteq DSPACE({\log }^{2}n)$；基本包含链把它置于 L 与 P 之间。