Loading AI tools
算法複雜度等級 来自维基百科，自由的百科全书
PSPACE是計算複雜度理論中能被確定型圖靈機利用多項式空間解決的判定問題集合，是Polynomial SPACE的簡稱。
 | 此條目包含過多行話或專業術語，可能需要簡化或提出進一步解釋。 (2013年9月24日) |
如果規定 為至多 空間內能被確定型圖靈機解決的問題的集合（ 是輸入大小 的函數），那麼，PSPACE可被形式化地定義為：
PSPACE真包含上下文有關語言，這種語言等價於線性有界非確定圖靈機。
儘管至今沒有證明，但一般認為，將P中的確定型圖靈機更改為非確定圖靈機後得到的NP類有成立。然而，對於PSPACE，將確定型圖靈機更改為非確定型圖靈機，得到的NPSPACE並不比PSPACE大。原因是根據薩維奇定理，，這個定理的結論指出，雖然非確定性問題需要更多時間解決，兩者的空間需求還是一致的。
已經證明PSPACE和NL、P、NP、PH、EXPTIME和EXPSPACE的關係 （注意，不是）：
目前已經知道，第一行和第二行中至少有一個包含關係為真包含，但是目前尚未證明任何一個。一般假定所有的包含關係均為真包含。
與此相反的是，第三行中的包含關係目前已證明均是真包含。第一個包含關係來源於對角論證法（根據空間層次定理，），而來源於薩維奇定理。第二個包含關係僅僅利用了空間層次定理。
在PSPACE中，最難的問題是PSPACE完全問題。參見PSPACE完全了解在PSPACE中但可能不在NP中的問題。
利用交替式圖靈機（ATM）的概念，PSPACE可被定義為一台ATM在多項式時間中解決的問題集合。這一複雜度類別也被稱為APTIME或者簡稱為AP。
複雜度理論中一個重要的結果為PSPACE與某個特定的互動式證明系統接受的所有語言等價，這個語言的集合也被定義為IP。在這一系統中，存在一個非常強大的證明者，這個證明者試圖說服一個機率多項式時間驗證者，某個字串在系統接受的語言中。如果字串屬於系統接受的語言，證明者應當能夠用較高的機率說服驗證者，否則只能至多用較低的機率說服。
PSPACE也等價於量子複雜度類別QIP。[11]
如果所有PSPACE中的問題都可以多項式時間歸約到某個問題，那麼，這個問題可以被定義為PSPACE難。
一種語言B為PSPACE完全，如果它在PSPACE中，並且為PSPACE難，即
其中，指的是存在從A到B的多項式時間歸約。PSPACE完全問題對於研究PSPACE中的問題非常重要，因為它們代表了PSPACE中最困難的問題。如果一個PSPACE完全問題得到了時間上高效的演算法，那麼，對所有PSPACE中的問題都可以有時間上高效的演算法，因為這些問題都能夠被多項式時間歸約到PSPACE完全問題。然而，這個性質對PSPACE難不成立，因為存在這樣的問題，它們可能屬於PSPACE難但不屬於PSPACE完全，因為這些問題不屬於PSPACE。
如果x屬於P，則P = PSPACE - Hard，那這個x就可稱為PSPACE - Hard。
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.
