{{Infobox Complexity Class
|class=
|image=
|long-name=
|description=
|external-urls=
|wheredefined=
|dtime=
|complete-class=
|complement-class=
|proper-supersets=
|improper-supersets=
|equals=
|related=
|notequals=
|improper-subsets=
|proper-subsets=
|properties=
|low-with=
|low-for=
|closed-reductions=
|closed-operations=
|canonical-problems=
|models=
}}
PSPACE (例子) |
| 完全集 | PSPACE完全 |
|---|
| 补类 | 自身 |
|---|
| 等价类 | AP[1], BPPSPACE[2], IP[3], NPSPACE[4], PPSPACE[5], SAPTIME[5] |
|---|
| DTIME |  ,  |
|---|
| 相关 | PTIME |
|---|
| 真包含于 | EXPSPACE[6] |
|---|
| 包含于 | AlmostPSPACE[7], EXPTIME, RG, QPSPACE[8] |
|---|
| 不等 | P-close, P/log |
|---|
| 子集 | CH[9], P^PP[10], P^#P[10], QSZK, RG[1] |
|---|
| 真子集 | NL[6] |
|---|
| 标准问题 | QSAT |
|---|
| 性质 | Syntactic |
|---|
| 被…低陷 | 自身 |
|---|
| 对…低陷 | 自身 |
|---|
| 封闭归约 | 多项式时间 |
|---|
| 计算模型 | 交替式图灵机, 图灵机 |
|---|
| 外部链接 | Complexity Zoo |
|---|
例子所用参考资料
- ^ Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
- ^ Complexity Zoo, [1], accessed Mars 25, 2009
- ^ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
- ^ Savitch's theorem
- ^ 5.0 5.1 Christos Papadimitriou. "Games against Nature". "Journal of Computer and System Sciences". 1985, 31.
- ^ 6.0 6.1 空间层次定理
- ^ Definition of Almost-PSPACE. PSPACE ⊆ PSPACE^A for every A.
- ^ Greg Kuperberg, Complexity Zoology: Active Inclusion Diagram, 2006, http://www.math.ucdavis.edu/~greg/zoology/diagram.xml
- ^ K. W. Wagner. The complexity of combinatorial problems with succinct representation. Informatica. 1986, 23: 325–356.
- ^ 10.0 10.1 S. Toda. On the computational power of PP and ⊕P. FOCS 1989. 1989: 514–519.
