Dark Mode

Tiao Zhuan Dao Nei Rong

Template:Infobox Complexity Class

Wei Ji Bai Ke ,Zi You De Bai Ke Quan Shu
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 (Li Zi )
Wan Quan Ji PSPACEWan Quan
Bu Lei Zi Shen
Deng Jie Lei AP[1], BPPSPACE[2], IP[3], NPSPACE[4], PPSPACE[5], SAPTIME[5]
DTIME n O ( 1 ) {\displaystyle n^{\Omega (1)}} , 2 n O ( 1 ) {\displaystyle 2^{n^{O(1)}}}
Xiang Guan PTIME
Zhen Bao Han Yu EXPSPACE[6]
Bao Han Yu AlmostPSPACE[7], EXPTIME, RG, QPSPACE[8]
Bu Deng P-close, P/log
Zi Ji CH[9], P^PP[10], P^#P[10], QSZK, RG[1]
Zhen Zi Ji NL[6]
Biao Zhun Wen Ti QSAT
Xing Zhi Syntactic
Bei ...Di Xian Zi Shen
Dui ...Di Xian Zi Shen
Feng Bi Gui Yue Duo Xiang Shi Shi Jian
Ji Suan Mo Xing Jiao Ti Shi Tu Ling Ji , Tu Ling Ji
Wai Bu Lian Jie Complexity Zoo

Li Zi Suo Yong Can Kao Zi Liao

[Bian Ji ]
  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 Kong Jian Ceng Ci Ding Li
  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.