PSPACE

維基百科,自由的百科全書
前往: 導覽搜尋
PSPACE
重要複雜度類之間的關係
多項式空間
完全集 PSPACE完全
補類 自身
等價類 AP[1], BPPSPACE[2], IP[3], NPSPACE[4], PPSPACE[5], SAPTIME[5]
DTIME n^{\Omega(1)}, 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

PSPACE計算複雜度理論中能被確定型圖靈機利用多項式空間解決的判定問題集合,是Polynomial SPACE的簡稱。

形式化定義[編輯]

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

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

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

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

與其它複雜度類的關係[編輯]

已經證明PSPACENLPNPPHEXPTIMEEXPSPACE的關係 (注意,\subsetneq不是\not\subseteq):

\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}
\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}
\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}

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

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

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

等價定義[編輯]

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

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

PSPACE也等價於量子複雜度類QIP[11]

PSPACE完全[編輯]

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

一種語言BPSPACE完全,如果它在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[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. ^ 5.0 5.1 Christos Papadimitriou. "Games against Nature". "Journal of Computer and System Sciences". 1985, 31. 
  6. ^ 6.0 6.1 空間層次定理
  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. ^ 10.0 10.1 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 arXiv:0907.4737 (July 2009)
  12. ^ "Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116."
  13. ^ 未來數學家的挑戰 - 楊照崑;楊重駿

參考文獻[編輯]

  1. 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.
  2. Christos Papadimitriou. Computational Complexity 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1.  Chapter 19: Polynomial space, pp. 455–490.
  3. Michael Sipser. Introduction to the Theory of Computation 2nd edition. Thomson Course Technology. 2006. ISBN 0-534-95097-3.  Chapter 8: Space Complexity

外部連結[編輯]