复杂度类 NL

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

设图有 $N$ 个顶点、编码长度为 $n$。有向可达性机器先保存当前顶点 $v=s$ 和计数器 $i=0$；若 $v=t$ 即接受，否则猜一个编号 $w$，扫描只读输入核实边 $(v,w)$，不合法便拒绝该分支，合法便更新 $v=w,i=i+1$。达到 $N-1$ 步仍未到 $t$ 就拒绝。每个编号和计数器各占 $O(\log N)\subseteq O(\log n)$ 位；历史顶点可以遗忘。若存在路径，删除重复顶点间的回路便得到至多 $N-1$ 条边的简单路，因此必有一条猜测分支接受。计数器也保证每条分支多项式时间停机，不能让“猜一条路径”无限走而不受控。若用确定性 BFS 保存整个 frontier 与 visited 集，通常需要线性空间，不能直接得到 L 上界。

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

NL 包含于 P 可由配置图具体模拟：把每个合法配置当作顶点、每一步合法转移当作有向边，从起始配置搜索能否到达接受配置。配置数和检查一条边的时间都是多项式，故确定性图搜索给出多项式时间上界；它可以使用多项式空间，因此没有证明 NL 等于 L。

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 确定化为平方空间。 则推出 $NL\subseteq DSPACE({\log }^{2}n)$；基本包含链把它置于 L 与 P 之间。