形式陈述

$\mathrm{NSPACE}(s(n))$ 包含由非确定性图灵机在每条计算分支上使用至多 $O(s(n))$ 工作空间判定的语言。作为判定器，机器在所有分支上停机；输入属于语言当且仅当至少一条分支接受，不属于语言时所有分支都拒绝。对 $s(n)\ge \log n$ 的标准模型，也可等价地在有限配置图中定义是否存在从起始配置到接受配置的路径。记

$$\mathrm{NL}=\mathrm{NSPACE}(\log n),\mathrm{NPSPACE}=\bigcup _{k\ge 1}\mathrm{NSPACE}(n^k).$$

Savitch 定理给出 $\mathrm{NSPACE}(s)\subseteq \mathrm{DSPACE}(s^2)$，故 $\mathrm{PSPACE}=\mathrm{NPSPACE}$。

直觉

空间可以重复使用。确定性模拟不必保存整棵非确定计算树，只需递归判断配置图中是否存在一条有界长度路径，因此平方空间便足够。

例子与边界

有向图可达性属于 NL：保存当前顶点，猜下一条边并计数至多 $|V|$ 步。简单深度优先搜索在显式图上可能用线性栈，但非确定路径证书只需对数空间保存当前位置。NSPACE 的空间界针对每条分支，不是所有分支内存之和。由 $PSPACE=NPSPACE$ 不能推出 $P=NP$，因为时间模拟仍可能指数。Immerman–Szelepcsényi 定理进一步给出 $NL=coNL$，但不是 NSPACE 定义本身。

推论与应用

NSPACE 用于描述可达性、自动机非空性和配置图搜索，是 Savitch 定理、NL 完全性与空间闭包理论的基础。

参考资料

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