PSPACE

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

${\displaystyle {\mbox{PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{SPACE}}(n^{k})}$ 

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

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

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

${\displaystyle {\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PH}}\subseteq {\mbox{PSPACE}}}$ 

${\displaystyle {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}\subseteq {\mbox{EXPSPACE}}}$ 

${\displaystyle {\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}}$ 

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

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

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

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

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

PSPACE也等价于量子复杂度类QIP。^[11]

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

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

${\displaystyle \forall {\mbox{A}}\in {\mbox{PSPACE}},{\mbox{A}}\leq _{p}{\mbox{B}}}$ 

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

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

例子

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

引用

来源

• Lecture slides on space complexity From University of Toronto
• Lecture slides on space complexity From Princeton University
• Complexity Zoo: PSPACE（页面存档备份，存于互联网档案馆）