Space Complexity & PSPACE

Space as a resource, Savitch's theorem, and PSPACE-completeness via TQBF.

The idea

Space complexity measures a computation by the memory it uses rather than the time it takes. Counting cells requires one convention: an input of length $n$ already occupies $n$ cells, so the input sits on a read-only tape that is not charged, and we count only the cells of a separate work tape.

Definition (Space classes).

$\mathrm{SPACE}(s(n))$ is the class of languages a deterministic Turing machine decides using $O(s(n))$ work cells, $\mathrm{NSPACE}(s(n))$ is the nondeterministic analogue, and $\mathrm{PSPACE} = \bigcup_{k \ge 1} \mathrm{SPACE}(n^{k}).$

Space behaves differently from time because space is reusable: a step once taken is spent, but a cell can be overwritten and used again, so a machine confined to polynomial space may still run for exponentially many steps. This reuse gives the space classes a character of their own. Nondeterminism buys less here: Savitch's theorem places $\mathrm{NSPACE}(s)$ inside $\mathrm{SPACE}(s^{2})$, and squaring a polynomial leaves it polynomial.

Corollary.

$\mathrm{PSPACE} = \mathrm{NPSPACE}$, where $\mathrm{NPSPACE} = \bigcup_{k \ge 1} \mathrm{NSPACE}(n^{k})$.

The problems complete for $\mathrm{PSPACE}$ are not searches for a single witness, as with $\mathsf{NP}$, but games of alternating moves, evaluated one branch at a time with the same cells reused for each. The figure evaluates one such game — a quantified formula $\forall x\, \exists y\ \varphi(x, y)$ — one branch at a time.

Ways to work on it

• Walkthrough. What polynomial space can compute, and the quantified-formula problem that is hardest in it.
• Practice. Answer a question about space classes or evaluate a small quantified Boolean formula.
• Hardest. Count a machine's configurations and evaluate a quantified Boolean formula with alternating quantifiers.

Not sure where to start? Take the ten-question placement test.