0
$\begingroup$

I am trying to understand why $BPP \subseteq EXP$. This question almost gives the answer (simulate $BPP$ machine on all possible toin cosses and then "act accordingly"). However, it is not clear to me what act accordingly means: I am thinking we need to count how many times the probabilistic Turing machine accepts and how many times it rejects and then act upon this information - but how exactly?

$\endgroup$
3
$\begingroup$

A $\mathsf{BPP}$ machine $A$ has randomness complexity $r(n)$ which is polynomial in $n$. Hence, an $\mathsf{EXP}$ machine $B$ can loop over all $2^{r(n)}$ values of the random tape of $A$, simulating $A$ with each random input (each simulation taking polynomial time), and count how many times $A$ accepts or rejects. The overall decision of $A$, then, is whichever of the two counters contains a larger value at the end of this process.

Interestingly, the same reasoning also explains why $\mathsf{PP}$ is contained in $\mathsf{EXP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.