PSPACE

PSPACE
多た项式空そら间 完全かんぜん集しゅう PSPACE完全かんぜん 补类 自身じしん 等とう价类 AP, BPPSPACE, IP, NPSPACE, PPSPACE, SAPTIME DTIME $n^{\Omega (1)}$, $2^{n^{O(1)}}$ 相あい关 PTIME 真ま包含ほうがん于 EXPSPACE 包含ほうがん于 近きんPSPACE, EXPTIME, RG, QPSPACE 不等ふとう P-close, P/log 子こ集しゅう CH, P^PP, P^#P, QSZK, RG[1] 真子しんじ集しゅう NL 标准问题 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}}$，这个定理ていり的てき结论指出さしで，虽然非ひ确定性せい问题需要じゅよう更さら多た时间解かい决，两者的てき空そら间需求もとめ还是一致いっち的てき。

与あずか其它复杂度ど类的关系

已やめ经证明あきらPSPACE和わNL、P、NP、PH、EXPTIME和わEXPSPACE的てき关系 （注意ちゅうい，$\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。

PSPACE - 完全かんぜん

主しゅ条目じょうもく：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。

参考さんこう文献ぶんけん

来らい源みなもと

• 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（页面存そん档备份，存そん于互联网档案あん馆）