Template:Infobox Complexity Class
外观
{{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完全 |
---|---|
补类 | 自身 |
等价类 | 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.