跳转到内容

模板:Infobox Complexity Class

维基百科,自由的百科全书
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 (例子)
完全集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

例子所用参考资料

[编辑]
  1. ^ Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
  2. ^ Complexity Zoo, [1], accessed Mars 25, 2009
  3. ^ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
  4. ^ Savitch's theorem
  5. ^ 5.0 5.1 Christos Papadimitriou. "Games against Nature". "Journal of Computer and System Sciences". 1985, 31. 
  6. ^ 6.0 6.1 空间层次定理
  7. ^ Definition of Almost-PSPACE. PSPACE ⊆ PSPACE^A for every A.
  8. ^ Greg Kuperberg, Complexity Zoology: Active Inclusion Diagram, 2006, http://www.math.ucdavis.edu/~greg/zoology/diagram.xml
  9. ^ K. W. Wagner. The complexity of combinatorial problems with succinct representation. Informatica. 1986, 23: 325–356. 
  10. ^ 10.0 10.1 S. Toda. On the computational power of PP and ⊕P. FOCS 1989. 1989: 514–519.