PSPACE

{{Infobox Complexity Class
|class=PSPACE
|image=
|long-name=多项式空间
|description=
|wheredefined=
|external-urls=[https://complexityzoo.net/Complexity_Zoo:P#pspace Complexity Zoo]
|dtime=n^{\Omega(1)}, 2^{n^{O(1)}}
|complete-class=PSPACE完全
|complement-class=自身
|proper-supersets=EXPSPACE
|improper-supersets=近PSPACE, EXPTIME, RG, QPSPACE
|equals=AP, BPPSPACE, IP, NPSPACE, PPSPACE, SAPTIME, P^PP, P^#P

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

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

:\forall\mbox{A}\in\mbox{PSPACE}, \mbox{A}\leq_p\mbox{B}

其中，\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。

参考文献
引用
来源
*
*
*
*
*
*

外部链接

• [https://web.archive.org/web/20110607195631/http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt Lecture slides on space complexity From University of Toronto]
• [https://web.archive.org/web/20060916231137/http://www.cs.princeton.edu/~wayne/kleinberg-tardos/09pspace.pdf Lecture slides on space complexity From Princeton University]

*[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pspace Complexity Zoo: PSPACE]