复杂度类 PSPACE

PSPACE 允许机器擦除旧信息、复用工作带，在指数大的隐式状态图或搜索树中逐路径探索。它适合描述“分支很多，但任何时刻只需记住当前路径”的计算，例如量词交替、规划状态搜索和有限博弈分析。

多项式空间并不等于“时间和空间都多项式”。枚举指数多个候选而逐个丢弃，或者递归遍历两棵子树并在返回后复用栈，都可能留在 PSPACE。反过来，若算法必须同时保存指数多个不同中间对象，就会越过多项式空间界。

逐层求值一个量化布尔公式 ​

考虑闭公式

内层公式要求 $x$ 与 $y$ 取值不同。对 $x=0$ 可选 $y=1$，对 $x=1$ 可选 $y=0$，所以公式为真。一般递归求值遇到 $\mathrm{\exists }$ 时顺序尝试两个值并取“或”，遇到 $\mathrm{\forall }$ 时顺序计算两个值并取“且”；第二个递归调用复用第一个调用释放的工作区。只需保存当前量词位置、部分赋值与递归栈，空间是公式长度的多项式，时间却可能达到 $2^n\mathrm{poly}(n)$。

这套机制给出 TQBF 属于 PSPACE；TQBF 的 PSPACE 完全性公理库TQBF 的 PSPACE 完全性PSPACE-completeness of TQBF · QBF is PSPACE-complete判定全量化布尔公式真值的问题在多项式时间归约下是 PSPACE 完全的。还需反向把任意多项式空间机器编码成量化公式。完全性不是从递归算法的上界一项自动得到的。

已知与未知的边界 ​

当前不知道 $\mathbf{P}=\mathbf{PSPACE}$ 是否成立，也不知道 $\mathbf{NP}=\mathbf{PSPACE}$。时间层级定理已知 $\mathbf{P}\ne \mathbf{EXP}$，所以链中至少有一处严格包含，但这不能指出 PSPACE 位于哪一侧。

PSPACE 只讨论判定语言。生成指数长度输出的任务即使能用小工作区流式产生结果，也需要另行说明输出空间和函数类；把整份指数长证书写进可回读工作带，便会超出多项式空间。通信、查询和性质测试使用不同资源单位，不能从 PSPACE 包含直接推出它们的界。

Savitch 定理公理库Savitch 定理Savitch's theorem对适当空间函数 s，NSPACE(s) 包含于 DSPACE(s²)。给出

对所有多项式预算取并便得 $\mathrm{NPSPACE}=\mathrm{PSPACE}$。平方仍是多项式，但确定化时间可高达 $2^{O(s(n{)}^2)}$，所以这个等式没有蕴含 P=NP。

若任一 PSPACE-complete 语言属于 P，则每个 PSPACE 语言经多项式时间归约后也属于 P，从而 $\mathbf{P}=\mathbf{PSPACE}$。规划、广义棋盘游戏与模型检查中的许多判定版本据此获得条件式难度解释。IP = PSPACE公理库IP = PSPACEIP equals PSPACE · Shamir's theorem多项式时间随机交互验证恰好能够判定全部多项式空间语言。还用交互证明给出同一语言类的另一种刻画；该结果依赖代数化协议，不是空间定义的直接推论。