形式陈述

复杂度类 $\mathrm{NL}$ 由可被非确定性图灵机使用 $O(\log n)$ 工作空间判定的语言组成：$x$ 属于语言当且仅当至少一条计算分支接受，所有分支都遵守空间界。其典型完全问题是有向可达性 $\mathrm{STCON}$：猜测从 $s$ 开始的下一顶点，并用 $O(\log n)$ 位保存当前顶点和至多 $|V|$ 的步数计数器。

直觉

非确定性允许算法只记住当前路径而不保存所有已访问顶点；存在一条正确猜测路径就足以接受。

例子与边界

有向图中若存在 $s$ 到 $t$ 的路，就存在长度小于 $|V|$ 的简单路，因此计数器可防止无限猜测。$\mathrm{L}\subseteq \mathrm{NL}$ 显然，但是否严格包含未知。Immerman–Szelepcsényi 定理给出 $\mathrm{NL}=\mathrm{coNL}$；该结论不能从“交换接受和拒绝状态”直接得到，因为非确定性采用存在分支语义。

推论与应用

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

参考资料

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