Savitch 定理

直接模拟非确定选择会面对一棵指数宽的树；保存一条完整接受路径也可能需要“路径长度乘配置长度”的指数空间。Savitch 的中点递归改问：两份配置之间是否有一条长度受限的路径。每次把允许长度减半，递归深度只剩路径长度的对数，也就是 $O(\log C)=O(s(n))$。

每层只保存端点 $u,v$、当前中点、枚举状态和常数个结果位，总计 $O(s(n))$ 位。沿一条深度优先递归链累加，空间满足

在 $i=O(s(n))$ 层后得到 $O(s(n{)}^2)$。指数多个候选中点从未同时驻留；算法用反复枚举的时间换掉了保存整张图或整条路径的空间。

四配置路径的递归拆分 ​

设配置图只有边

因为共有四个配置，检查长度至多 $4$ 的路径可调用 $R(u,v,2)$。顶层枚举到中点 $b$ 时，左侧 $R(u,b,1)$ 检查至多两步的 $u\to a\to b$，右侧 $R(b,v,1)$ 检查一步边 $b\to v$；两者再降到一步基例。算法在任一时刻只保留当前递归链上的端点和中点，没有保存完整路径 $(u,a,b,v)$ 的数组。

时间代价 ​

若每层枚举至多 $C(n)$ 个中点，粗略时间递推为

深度为 $O(\log C)$，所以时间可达

取 $s(n)=\log n$ 时，这是 $n^{O(\log n)}$ 的拟多项式时间，而不是多项式时间。平方空间确定化不能照搬成多项式时间去非确定化。

假设与结论边界 ​

$s(n)\ge \log n$ 使输入头位置和配置计数可纳入 $O(s(n))$ 位；低于该阈值时，模型约定会影响陈述。定理也没有证明 $\mathrm{NSPACE}(s)=\mathrm{DSPACE}(s)$：取 $s=\log n$ 只得到 $\mathrm{NL}\subseteq \mathrm{DSPACE}({\log }^{2}n)$，并未解决 L 是否等于 NL。

对任意 $k$ 应用定理，

再结合每台确定机器都可视为不分支的非确定机器，得到

这解释了为什么非确定性不会扩大多项式空间类，却没有推出 P=NP：确定模拟付出的时间可能是 $2^{n^{O(1)}}$。Savitch 的递归可达法也成为隐式指数图上小空间搜索的标准范式；Immerman–Szelepcsényi 定理公理库Immerman–Szelepcsényi 定理Immerman–Szelepcsényi theorem · NL equals coNL非确定性空间类在补运算下封闭，特别地 NL 等于 coNL。关于 NSPACE 对补封闭的结论则使用另一套计数思路，不能从本定理直接读出。