PSPACE

PSPACE is the class of decision problems solvable by a deterministic Turing machine using only polynomial space in the length of the input. That is, there exists a polynomial p such that the machine never uses more than p(n) cells of memory on input of length n, regardless of time taken. Time may be exponential in the input size.

By Savitch's theorem, PSPACE equals NPSPACE, so nondeterministic polynomial space computations have the same power as deterministic ones. PSPACE is closed under complement, and it contains P and NP; in particular, PSPACE = co-PSPACE. It is known to be contained in EXPTIME, since any polynomial-space computation can be simulated in exponential time.

The canonical PSPACE-complete problem is TQBF, the true quantified Boolean formula problem, equivalently the fully quantified Boolean formula with alternating quantifiers. Other PSPACE-complete problems include Generalized Geography on directed graphs and certain planning and game-theoretic problems with polynomially bounded structure. A problem is PSPACE-complete if it lies in PSPACE and every problem in PSPACE reduces to it in polynomial time.

Commonly cited relationships among complexity classes are P ⊆ NP ⊆ PSPACE ⊆ EXP, with the exact strictness of several inclusions unknown. The study of PSPACE helps understand the inherent difficulty of problems where memory, rather than time, is the limiting resource. PSPACE-complete problems are often used to model strategic reasoning with bounded resources, such as alternating quantifiers or sequential moves with memory of past states.