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

Quick Facts 完全集, 補類 ...
PSPACE
重要複雜度類之間的關係
完全集PSPACE完全
補類自身
等價類AP[1], BPPSPACE[2], IP[3], NPSPACE[4], PPSPACE[5], SAPTIME[5]
DTIME,
相關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
Close

形式化定義

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

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

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

與其它複雜度類的關係

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

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

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

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

等價定義

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

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

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

PSPACE - 完全

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

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

其中,指的是存在從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]

參考文獻

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.