形式陈述

复杂度类

$$\mathrm{PSPACE}=\bigcup _{k\ge 1}\mathrm{DSPACE}(n^k)$$

由可在确定性图灵机上使用多项式工作空间判定的语言组成。因为一台在 $s(n)$ 空间内停机的确定性机器若不重复配置，运行时间至多指数于 $s(n)$，故

$$\mathrm{P}\subseteq \mathrm{PSPACE}\subseteq \mathrm{EXPTIME}.$$

由 Savitch 定理，$\mathrm{NPSPACE}=\mathrm{PSPACE}$。

直觉

PSPACE 限制同时保留的信息量，不限制重复利用同一存储所花的时间。因此算法可以在多项式内存中遍历指数大的隐式状态空间。

例子与边界

量化布尔公式 QBF/TQBF 是 PSPACE-complete：可递归尝试量词赋值而只保存当前深度路径。PSPACE 不等于“时间和空间都多项式”；成员算法可能需要指数时间。当前已知 $\mathrm{P}\subseteq \mathrm{PSPACE}$，但不知道是否严格。

推论与应用

PSPACE 刻画规划、博弈、模型检测和全称/存在交替搜索的典型复杂度。PSPACE-complete 问题若有多项式时间算法，将推出 $\mathrm{P}=\mathrm{PSPACE}$。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 4。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§8.2。