 | |
| External pages | Complexity Zoo |
|---|---|
| Complete class | PSPACE-complete |
| Complement class | self |
| Equalities | AP [1], BPPSPACE [2], IP [3], NPSPACE [4], PPSPACE [5], SAPTIME [5] |
| DTIME | , |
| Related | PTIME |
| Proper supersets | EXPSPACE [6] |
| Improper supersets | AlmostPSPACE [7], EXPTIME, RG, QPSPACE [8] |
| Inequalities | P-close, P/log |
| Improper subsets | CH [9], P^ PP [10], P^ #P [10], QSZK, RG[1] |
| Proper subsets | NL [6] |
| Canonical problems | QSAT |
| Properties | Syntactic |
| Low with | self |
| Low for | self |
| Closed reductions | Poly-time |
| Models | Alternating Turing machine, Turing machine |
User:C. lorenz/Template:Infobox Complexity Class
- ^ 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
- ^ a b Christos Papadimitriou (1985). ""Games against Nature"". "Journal of Computer and System Sciences". 31.
- ^ a b Space hierarchy theorem
- ^ 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 (1986). "The complexity of combinatorial problems with succinct representation". Informatica. 23: 325–356.
- ^ a b S. Toda (1989). "On the computational power of PP and ⊕P". FOCS 1989: 514–519.
|
| |
| External pages | Complexity Zoo |
|---|---|
| Complete class | PSPACE-complete |
| Complement class | self |
| Equalities | AP [1], BPPSPACE [2], IP [3], NPSPACE [4], PPSPACE [5], SAPTIME [5] |
| DTIME | , |
| Related | PTIME |
| Proper supersets | EXPSPACE [6] |
| Improper supersets | AlmostPSPACE [7], EXPTIME, RG, QPSPACE [8] |
| Inequalities | P-close, P/log |
| Improper subsets | CH [9], P^ PP [10], P^ #P [10], QSZK, RG[1] |
| Proper subsets | NL [6] |
| Canonical problems | QSAT |
| Properties | Syntactic |
| Low with | self |
| Low for | self |
| Closed reductions | Poly-time |
| Models | Alternating Turing machine, Turing machine |
User:C. lorenz/Template:Infobox Complexity Class
- ^ 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
- ^ a b Christos Papadimitriou (1985). ""Games against Nature"". "Journal of Computer and System Sciences". 31.
- ^ a b Space hierarchy theorem
- ^ 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 (1986). "The complexity of combinatorial problems with succinct representation". Informatica. 23: 325–356.
- ^ a b S. Toda (1989). "On the computational power of PP and ⊕P". FOCS 1989: 514–519.