PSPACE复杂度类

PSPACE是确定性多项式空间复杂度类，即所有能由总会停机的确定性图灵机，以输入长度n的某个多项式作为空间上界来判定的语言。可写为所有常数k对应SPACE(n^k)的并集。这里讨论的是算法最坏情况下使用的空间，并不要求所有问题共用同一个指数k。

空间能够复用：检查一个候选答案后，可以擦除中间结果，再检查下一个。比如SAT可逐一遍历变量赋值，只留下当前赋值及求值所需存储。赋值数可能指数增长，但这些赋值不必同时保存在内存里，所以这种穷举仍可使用多项式空间。

参考：[1] [2]

完全量化布尔公式中，每个变量都由存在量词或全称量词约束。求值时，遇到存在量词就分别尝试0、1，有一支真便为真；遇到全称量词则要求两支都真。量词顺序不能随意交换，例如∀x∃y(x=y)为真，而∃y∀x(x=y)为假。

算法可深度优先计算量词树，只保存当前赋值、递归位置和已得到的局部结果。处理完一支就回收其存储，再处理另一支。递归深度不超过变量数，故工作空间可保持多项式；但是分支总数可能很大，空间上界并不同时给出多项式时间上界。

参考：[2]

判断一个完全量化布尔公式是否为真的TQBF问题，不仅属于PSPACE，还是多项式时间多一归约下的PSPACE完全问题。这意味着任何多项式空间判定问题，都可以高效编码为一个保持答案的量化公式。只展示递归求值算法，只证明了成员资格，完全性还需要这项归约结论。

若TQBF存在确定性多项式时间算法，则P=PSPACE；若它属于NP，则NP=PSPACE。这些是条件推论，不是已经建立的分离结果。完全问题提供了比较整个类能力的代表，但不意味着每一条量化公式都难求值。

参考：[3]

已知P⊆NP⊆PSPACE⊆EXP。NP包含于PSPACE，可通过逐一枚举多项式长度证书并复用验证空间来理解。多项式空间确定性机器的配置只有指数多个；它若总会停机，就不能重复相同配置而无限循环，因此有指数时间上界。

P是否等于PSPACE、NP是否等于PSPACE、PSPACE是否等于EXP仍未确定，不能把包含符号擅自改为严格包含。另一方面，Savitch定理把非确定性空间模拟为平方确定性空间，确实推出PSPACE=NPSPACE。PSPACE还对取补封闭，因为确定性判定器总会停机，交换最后的接受与拒绝不会增加空间量级。

参考：[1] [2] [3]