The classes PSPACE and NPSPACE

The class PSPACE is the union of all deterministic polynomial-space classes:

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}:={\bigcup }_{p\text{ polynomial}}\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(p(n))\mathrm{.}$

The class NPSPACE is the union of all nondeterministic polynomial-space classes:

$\mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}:={\bigcup }_{p\text{ polynomial}}\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(p(n))\mathrm{.}$

Equivalently, a language $L$ lies in PSPACE when there is a deterministic multitape Turing machine deciding $L$ using at most $O(n^c)$ space for some constant $c$, and similarly $L$ lies in NPSPACE when there is such a nondeterministic decider. The meanings of $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))$ and $\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))$ are those of The classes DTIME, NTIME, DSPACE, and NSPACE.

• The page uses polynomial space rather than a single fixed bound because closure and completeness statements are stated for the whole class.
• No closure under complement is built into the definition of NPSPACE; that is a later theorem.