BPP ⊆ PSPACE

Inclusion · folklore

Statement

BPP $\subseteq$ PSPACE — folklore.

Sketch

Run the $\mathbf{BPP}$ 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 majority accept.