PSPACE

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.If we denote by SPACE(f(n)), the set of all problems that can be solved by Turing machines using O(f(n)) space for some function f of the input size n, then we can define PSPACE formally as[1] It turns out that allowing the Turing machine to be nondeterministic does not add any extra power.[citation needed] The following relations are known between PSPACE and the complexity classes NL, P, NP, PH, EXPTIME and EXPSPACE (note that ⊊ denotes strict containment, not to be confused with ⊈): From the third line, it follows that both in the first and in the second line, at least one of the set containments must be strict, but it is not known which.A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular interactive proof system, the one defining the class IP.In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language.
Inclusions of complexity classes including P , NP , co-NP , BPP , P/poly , PH , and PSPACE
A representation of the relation among complexity classes
Polynomial ringP/poly(more unsolved problems in computer science)computational complexity theorydecision problemsTuring machinepolynomialamount of spaceTuring machinesnondeterministicSavitch's theoremnondeterministic Turing machineit may use much more timecomplementsEXPTIMEEXPSPACEspace hierarchy theoremPSPACE-completecomplementationKleene staralternating Turing machinedescriptive complexitysecond-order logictransitive closureinteractive proof systemclosed timelike curvesquantum computerspolynomial-time many-one reductionquantified Boolean formula problemJohn WatrousBibcodeArora, SanjeevCambridge University PressSipser, MichaelPapadimitriou, ChristosComplexity ZooComplexity classesDLOGTIMENL-completeP-completeNP-completeNP-hardco-NP-complete#P-completeNEXPTIME2-EXPTIMEELEMENTARYPolynomial hierarchyExponential hierarchyGrzegorczyk hierarchyArithmetical hierarchyBoolean hierarchyDSPACENSPACEProbabilistically checkable proofList of complexity classes