PSPACE

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。

PSPACE

完全集	PSPACE完全
补类	自身
等价类	AP[1], BPPSPACE[2], IP[3], NPSPACE[4], PPSPACE[5], SAPTIME[5]
DTIME	${\displaystyle n^{\Omega (1)}}$, ${\displaystyle 2^{n^{O(1)}}}$
相关	PTIME
真包含于	EXPSPACE[6]
包含于	近PSPACE[7], EXPTIME, RG, QPSPACE[8]
不等	P-close, P/log
子集	CH[9], P^PP[10], P^#P[10], QSZK, RG[1]
真子集	NL[6]
标准问题	QSAT
被…低陷	自身
对…低陷	自身
封闭归约	多项式时间
计算模型	交替式图灵机, 图灵机
外部链接	Complexity Zoo

形式化定义

如果规定 ${\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完全

如果所有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。

PSPACE - Hard

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

例子

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

参考文献

引用

1. Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
2. Complexity Zoo, [1] （页面存档备份，存于互联网档案馆）, accessed Mars 25, 2009
3. Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
4. 萨维奇定理
5. 赫里斯托斯·帕帕季米特里乌. "Games against Nature". "Journal of Computer and System Sciences". 1985, 31.
6. 空间层次定理
7. Definition of Almost-PSPACE. PSPACE ⊆ PSPACE^A for every A.
8. Greg Kuperberg, Complexity Zoology: Active Inclusion Diagram, 2006, http://www.math.ucdavis.edu/~greg/zoology/diagram.xml （页面存档备份，存于互联网档案馆）
9. K. W. Wagner. The complexity of combinatorial problems with succinct representation. Informatica. 1986, 23: 325–356.
10. S. Toda. On the computational power of PP and ⊕P. FOCS 1989. 1989: 514–519.
11. QIP = PSPACE, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous（英语：John Watrous (computer scientist)） arXiv:0907.4737 (July 2009)
12. "Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116."
13. 未來數學家的挑戰 - 楊照崑;楊重駿. [2013-05-11]. （原始内容存档于2018-07-12）.

来源

• Michael Sipser（英语：Michael Sipser）. Sections 8.2–8.3 (The Class PSPACE, PSPACE-completeness). Introduction to the Theory of Computation. PWS Publishing. 1997: 281–294. ISBN 0-534-94728-X.
• Christos Papadimitriou. 19: Polynomial space. Computational Complexity 1st. Addison Wesley. 1993: 455–490. ISBN 0-201-53082-1.
• Michael Sipser. 8: Space Complexity. Introduction to the Theory of Computation 2nd. Thomson Course Technology. 2006. ISBN 0-534-95097-3.
• Arora, Sanjeev; Barak, Boaz. Computational complexity. A modern approach. Cambridge University Press. 2009. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• Papadimitriou, Christos. 19: Polynomial space. Computational Complexity 1st. Addison Wesley. 1993: 455–490. ISBN 0-201-53082-1.
• Sipser, Michael. 8: Space Complexity. Introduction to the Theory of Computation 2nd. Thomson Course Technology. 2006. ISBN 0-534-95097-3.

外部链接

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