萨维奇定理(Savitch's Theorem)

萨维奇定理(Savitch's Theorem)是计算复杂度理论中关于空间资源的重要定理,由沃尔特·萨维奇(Walter Savitch)于1970年证明。它表明,任何用 f(n) 空间的非确定图灵机所能解决的问题,都能由一个确定图灵机在 f(n) 的平方级空间内解决,前提是 f(n) 不小于对数级并满足一定良性条件。

概述

该定理揭示了在空间度量下,非确定性带来的优势远小于在时间度量下。对于时间复杂度,人们普遍相信非确定性可能带来指数级差异,即 P 是否等于 NP 尚未解决;而对于空间复杂度,萨维奇定理给出了明确答案:非确定空间与确定空间之间只差一个平方,属于多项式关系。

核心原理

• 可达性视角:非确定机的计算被看作在其状态构型图中寻找从起点到接受点的路径。
• 分治递归:通过判断是否存在长度不超过某值的路径,把问题递归地对半拆分。
• 复用空间:递归各分支顺序执行并复用同一块空间,从而把空间控制在平方级。
• 以时间换空间:该方法节省了空间,但运行时间可能显著增加。

应用场景

萨维奇定理最著名的推论是 PSPACE 等于 NPSPACE,即多项式空间下确定与非确定能力相同,这一点与时间层次的开放问题形成鲜明对比。它还说明了有向图可达性问题可以在对数平方空间内确定性求解,是空间复杂度类关系研究的基石之一。

常见问题

问:为什么空间里非确定性没那么强?答:因为空间可以被反复复用,确定机能系统地枚举并复用同一块内存来模拟所有非确定选择,代价只是平方级空间和更多时间。

问:它证明了 P 等于 NP 吗?答:没有。它只关于空间复杂度,给出 PSPACE 等于 NPSPACE,并未触及时间上的 P 与 NP 问题。