PP ⊆ PSPACE

Inclusion · folklore

Statement

PP $\subseteq$ PSPACE — folklore.

Sketch

Run the $\mathbf{PP}$ machine on each of its $2^{\mathrm{poly}(n)}$ random strings in turn, reusing space across runs and keeping a $\mathrm{poly}(n)$-bit count of accepting runs; accept iff a strict majority accept.