形式化定义

如果规定 SPACE ( t ( n ) ) {\displaystyle {\mbox{SPACE}}(t(n))} 为至多 t ( n ) {\displaystyle t(n)} 空间内能被确定型图灵机解决的问题的集合（ t {\displaystyle t} 是输入大小 n {\displaystyle n} 的函数），那么， PSPACE 可被形式化地定义为：

PSPACE 真包含上下文有关语言，这种语言等价于线性有界非确定图灵机。

尽管至今没有证明，但一般认为，将 P 中的确定型图灵机更改为非确定图灵机后得到的 类有 P ⊊ ⊊ --> {\displaystyle {\mbox{P}}\subsetneq {\mbox{}}} 成立。然而，对于 PSPACE ，将确定型图灵机更改为非确定型图灵机，得到的 SPACE 并不比 PSPACE 大。原因是根据萨维奇定理， PSPACE = SPACE {\displaystyle {\mbox{PSPACE}}={\mbox{SPACE}}} ，这个定理的结论指出，虽然非确定性问题需要更多时间解决，两者的空间需求还是一致的。

与其它复杂度类的关系

已经证明 PSPACE 和 NL 、 P 、 、 PH 、 EXPTIME 和 EXPSPACE 的关系 （注意， ⊊ ⊊ --> {\displaystyle \subsetneq } 不是 ⊈ {\displaystyle \not \subseteq } ）：

目前已经知道，第一行和第二行中至少有一个包含关系为真包含，但是目前尚未证明任何一个。一般假定所有的包含关系均为真包含。

与此相反的是，第三行中的包含关系目前已证明均是真包含。第一个包含关系来源于对角论证法（根据空间层次定理， NL ⊊ ⊊ --> SPACE {\displaystyle {\mbox{NL}}\subsetneq {\mbox{SPACE}}} ），而 PSPACE = SPACE {\displaystyle {\mbox{PSPACE}}={\mbox{SPACE}}} 来源于萨维奇定理。第二个包含关系仅仅利用了空间层次定理。

在 PSPACE 中，最难的问题是 PSPACE完全 问题。参见 PSPACE完全 了解在 PSPACE 中但可能不在 中的问题。

等价定义

利用交替式图灵机（ATM）的概念， PSPACE 可被定义为一台ATM在多项式时间中解决的问题集合。这一复杂度类也被称为 APTIME 或者简称为 AP 。

复杂度理论中一个重要的结果为 PSPACE 与某个特定的交互式证明系统接受的所有语言等价，这个语言的集合也被定义为 IP 。在这一系统中，存在一个非常强大的证明者，这个证明者试图说服一个概率多项式时间验证者，某个字符串在系统接受的语言中。如果字符串属于系统接受的语言，证明者应当能够用较高的概率说服验证者，否则只能至多用较低的概率说服。

PSPACE 也等价于量子复杂度类 QIP 。

PSPACE完全

如果所有 PSPACE 中的问题都可以多项式时间归约到某个问题，那么，这个问题可以被定义为 PSPACE难 。

一种语言 B 为 PSPACE完全 ，如果它在 PSPACE 中，并且为 PSPACE难 ，即

其中， A ≤ ≤ --> p B {\displaystyle {\mbox{A}}\leq _{p}{\mbox{B}}} 指的是存在从A到B的多项式时间归约。 PSPACE完全 问题对于研究 PSPACE 中的问题非常重要，因为它们代表了 PSPACE 中最困难的问题。如果一个 PSPACE完全 问题得到了时间上高效的算法，那么，对所有 PSPACE 中的问题都可以有时间上高效的算法，因为这些问题都能够被多项式时间归约到 PSPACE完全 问题。然而，这个性质对 PSPACE难 不成立，因为存在这样的问题，它们可能属于 PSPACE难 但不属于 PSPACE完全 ，因为这些问题不属于 PSPACE 。

PSPACE - Hard

如果x属于P，则P = PSPACE - Hard，那这个x就可称为PSPACE - Hard。

例子

围棋的复杂度已于1978年被Robertson与Munro证明为PSPACE-hard 。

参考文献

Michael Sipser （ 英语 ： Michael Sipser ） . Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.

Christos Papadimitriou. Computational Complexity t edition. Addison Wesley. 1993. ISBN 0-201-53082-1. 引文格式1维护：冗余文本 (link) Chapter 19: Polynomial space, pp. 455–490.

Michael Sipser. Introduction to the Theory of Computation 2nd edition. Thomson Course Technology. 2006. ISBN 0-534-95097-3. 引文格式1维护：冗余文本 (link) Chapter 8: Space Complexity

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。