Jump to content

User:C. lorenz/sandbox

From Wikipedia, the free encyclopedia
PSPACE
External pagesComplexity Zoo
Complete classPSPACE-complete
Complement classself
EqualitiesAP[1], BPPSPACE[2], IP[3], NPSPACE[4], PPSPACE[5], SAPTIME[5]
DTIME,
RelatedPTIME
Proper supersetsEXPSPACE[6]
Improper supersetsAlmostPSPACE[7], EXPTIME, RG, QPSPACE[8]
InequalitiesP-close, P/log
Improper subsetsCH[9], P^PP[10], P^#P[10], QSZK, RG[1]
Proper subsetsNL[6]
Canonical problemsQSAT
PropertiesSyntactic
Low withself
Low forself
Closed reductionsPoly-time
ModelsAlternating Turing machine, Turing machine

User:C. lorenz/Template:Infobox Complexity Class

  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. ^ a b Christos Papadimitriou (1985). ""Games against Nature"". "Journal of Computer and System Sciences". 31.
  6. ^ a b Space hierarchy theorem
  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 (1986). "The complexity of combinatorial problems with succinct representation". Informatica. 23: 325–356.
  10. ^ a b S. Toda (1989). "On the computational power of PP and ⊕P". FOCS 1989: 514–519.