PSPACE

PSPACE

重要複雜度類之間的關係
DTIME	<math>n^{\Omega(1)}</math>, <math>2^{n^{O(1)
外部鏈接	Complexity Zoo

</math>

|complete-class=PSPACE完全 |complement-class=自身 |proper-supersets=EXPSPACE |improper-supersets=近PSPACE, EXPTIME, RG, QPSPACE |equals=AP, BPPSPACE, IP, NPSPACE, PPSPACE, SAPTIME |related=PTIME |notequals=P-close, P/log |improper-subsets=CH, P^PP, P^#P, QSZK, RG[1] |proper-subsets=NL |properties= |low-with=自身 |low-for=自身 |closed-reductions=多項式時間 |closed-operations= |canonical-problems=QSAT |models=交替式圖靈機, 圖靈機 }} PSPACE是計算複雜度理論中能被確定型圖靈機利用多項式空間解決的判定問題集合，是Polynomial SPACE的簡稱。

形式化定義

如果規定 <math>\mbox{SPACE}(t(n))</math> 為至多 <math>t(n)</math> 空間內能被確定型圖靈機解決的問題的集合（<math>t</math> 是輸入大小 <math>n</math> 的函數），那麼，PSPACE可被形式化地定義為：

<math>\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)</math>

PSPACE真包含上下文有關語言，這種語言等價於線性有界非確定圖靈機。

儘管至今沒有證明，但一般認為，將P中的確定型圖靈機更改為非確定圖靈機後得到的NP類有<math>\mbox{P} \subsetneq \mbox{NP}</math>成立。然而，對於PSPACE，將確定型圖靈機更改為非確定型圖靈機，得到的NPSPACE並不比PSPACE大。原因是根據薩維奇定理，<math>\mbox{PSPACE} = \mbox{NPSPACE}</math>，這個定理的結論指出，雖然非確定性問題需要更多時間解決，兩者的空間需求還是一致的。

與其它複雜度類的關係

已經證明PSPACE和NL、P、NP、PH、EXPTIME和EXPSPACE的關係 （注意，<math>\subsetneq</math>不是<math>\not\subseteq</math>）：

<math>\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}</math>

<math>\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}</math>

<math>\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}</math>

目前已經知道，第一行和第二行中至少有一個包含關係為真包含，但是目前尚未證明任何一個。一般假定所有的包含關係均為真包含。

與此相反的是，第三行中的包含關係目前已證明均是真包含。第一個包含關係來源於對角論證法（根據空間層次定理，<math>\mbox{NL} \subsetneq \mbox{NPSPACE}</math>），而<math>\mbox{PSPACE} = \mbox{NPSPACE}</math>來源於薩維奇定理。第二個包含關係僅僅利用了空間層次定理。

在PSPACE中，最難的問題是PSPACE完全問題。參見PSPACE完全了解在PSPACE中但可能不在NP中的問題。

等價定義

利用交替式圖靈機（ATM）的概念，PSPACE可被定義為一台ATM在多項式時間中解決的問題集合。這一複雜度類也被稱為APTIME或者簡稱為AP。

複雜度理論中一個重要的結果為PSPACE與某個特定的交互式證明系統接受的所有語言等價，這個語言的集合也被定義為IP。在這一系統中，存在一個非常強大的證明者，這個證明者試圖說服一個概率多項式時間驗證者，某個字符串在系統接受的語言中。如果字符串屬於系統接受的語言，證明者應當能夠用較高的概率說服驗證者，否則只能至多用較低的概率說服。

PSPACE也等價於量子複雜度類QIP。

PSPACE - 完全

主條目：PSPACE完全

如果所有PSPACE中的問題都可以多項式時間歸約到某個問題，那麼，這個問題可以被定義為PSPACE難。

一種語言B為PSPACE完全，如果它在PSPACE中，並且為PSPACE難，即

<math>\forall\mbox{A}\in\mbox{PSPACE}, \mbox{A}\leq_p\mbox{B}</math>

其中，<math>\mbox{A}\leq_p\mbox{B}</math>指的是存在從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. 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（頁面存檔備份，存於網際網路檔案館）