PSPACE ⊆ EXP

Inclusion · folklore

Statement

PSPACE $\subseteq$ EXP — folklore.

Sketch

A deterministic machine running in space $p(n)=\mathrm{poly}(n)$ has at most $2^{O(p(n))}$ configurations, so on any input it halts within $2^{O(p(n))}$ steps or never; simulating it for that many steps decides its language in time $2^{\mathrm{poly}(n)}$.