PSPACE

Remarks

Example: the set of propositional tautologies lies in PSPACE. For a formula $\varphi$ with $n$ variables, a machine runs through all $2^n$ assignments, keeping only the current one, and evaluates $\varphi$ at each. The space used is polynomial in the length of $\varphi$, though the time may be exponential.

Non-example: a machine that stores a table with one entry for each of the $2^n$ assignments uses exponential space. It does not show that its language lies in PSPACE.

One has $\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}$, where P is the class P and NP is the class NP. A machine with polynomial space has at most exponentially many configurations, so PSPACE lies in exponential time. By Savitch's theorem, PSPACE also equals the class NPSPACE defined with nondeterministic machines.