非确定性空间复杂性类

非确定空间把计算看成有限配置图上的路径搜索。机器不保存整棵分支树，只在一条候选路径上维护当前配置；成员输入只需某条路径到达接受配置。即使图有指数多个节点，一份配置仍只有 $O(s(n))$ 位，这为后续用空间换时间的确定性模拟留下了余地。

与确定性空间类理路确定性空间复杂性类Deterministic space class · DSPACE由确定性图灵机在给定工作空间界内判定的语言集合。相比，计费单位没有变化，变化的是配置图的出度和接受量词。确定机器每个配置至多一个后继，非确定机器则可以选择后继，但不存在“把所有分支内存加总”的共享机器。

有向可达性的对数空间算法 ​

设图的顶点为 $\{s,a,b,t\}$，边为

机器保存当前顶点和一个不超过 $|V|-1$ 的步数计数器，非确定地选择一条出边。分支 $s\to a\to t$ 接受；分支 $s\to b\to b\to \cdots$ 在计数器到达 $3$ 后拒绝。一般 $n$ 顶点图中，若存在路径就存在不重复顶点、长度至多 $n-1$ 的路径，当前位置与计数器各需 $O(\log n)$ 位；检查所猜边时只需扫描只读输入。因此有向 STCON 属于 NL。

分支与停机边界 ​

一条分支使用 $10$ 个格、另一条使用 $20$ 个格时，本次输入的空间是 $20$，不是 $30$。分支可能运行指数步而不增加工作区域；NSPACE 不是并行内存或时间复杂度。

若只给 recognizer，允许非成员输入上某些分支永不停止，就不能直接把它当作 NSPACE 判定机。必须先在 $s(n)\ge \log n$、预算可构造等标准条件下利用配置去环和时钟，让每条分支停机，再调用本页的类与闭包结论。

确定机器是非确定机器的特例，故

常用并集类为

Savitch 定理理路Savitch 定理Savitch's theorem通过配置可达性的中点递归与工作区复用，把非确定空间 s 确定化为平方空间。以平方空间确定化配置可达性，推出 $\mathrm{NPSPACE}=\mathrm{PSPACE}$。模拟时间可以很大，不能据此推出 P=NP。

Immerman–Szelepcsényi 定理理路Immerman–Szelepcsényi 定理Immerman–Szelepcsényi theorem · NL equals coNL非确定性空间类在补运算下封闭，特别地 NL 等于 coNL。证明对空间可构造的 $s(n)\ge \log n$，NSPACE 对补封闭；它使用更精细的计数式可达性方法，并非定义的直接改写。