Question

Show that BPP$\mathbf{\subseteq }$PSPACE.

Short answer

We can show that$\mathit{B}\mathit{P}\mathit{P}\mathbf{\subseteq }\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}$ by converting BPP into PSPACE.

Step-by-step solution

Understanding and solving the problem using polynomial time

Consider M be a probabilistic TM which runs on polynomial time.

Therefore, .$\mathbf{M}\in \mathbf{BPP}$ can be modified so that M makes exactly${\mathbf{a}}^{\mathbf{c}}$ coin tosses in each branch of its computation, for any constant C

Understanding the performing of the task

Since, there are total of${\mathbf{2}}^{\mathbf{\left(}{\mathbf{a}}^{\mathbf{0}}\mathbf{\right)}}$ computation path, problem which is determining probability that M accepts its input is reduces to counting how many branches B are accepting and comparing this number with$\mathbf{p}\mathbf{=}\mathbf{\left(}\frac{\mathbf{3}}{\mathbf{4}}\mathbf{\right)}\mathbf{.}{\mathbf{2}}^{\mathbf{\left(}{\mathbf{a}}^{\mathbf{0}}\mathbf{\right)}}$

If,then accept otherwise reject. Now the given deterministic task can be performed in the polynomial space by generating all possible paths sequentially following M’s program but recycling the space used by the previous path.

Therefore, the problem of BPP is converted into PSPACE. Hence,

$\mathbf{BPP}\mathbf{\subseteq }\mathbf{PSPACE}$