Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is equivalent.

  1. If we run machine $A$ on $x$ it can accept a word $x$ with probability $0.5$. Now we can run our $EXP$-machine. It try every possible toin-cosses-result so it compute an average probability of accepting of $x$.

  2. I don't see why it works equivalently- even if the $EXP$-machine has coin-toesses as input, it should be random in any way.


1 Answer 1


You are confused about the definition of when a language is in a class. You show that a language $L\subseteq \{0,1\}^\ast$ is in $P$, for example, by describing a Turing Machine with the following properties:

  1. It is deterministic
  2. It runs in polynomial time
  3. It solves $L$

The classes $BPP$ and $EXP$ have similar definitions. The Complexity Zoo has a (very long) list of all the complexity classes.

The proof you cite works by following the definition of $EXP$ very closely: to show that $L\in EXP$, it describes a Turing Machine which (1) is deterministic, (2) runs in exponential time and (3) solves $L$. Showing this is relatively straightforward: it simulates the random machine for all possible random seeds, counts how many of those computations accept and how many reject, and then acts accordingly. This new algorithm satisfies the three properties above: we now know that there is a Turing Machine which is deterministic, runs in exponential time, and solves $L$. Now the proof is done. $\square$

The confusion may be that you do not need an equivalent machine (one that is also random, or that also sometimes errs, etc.), you only need to look closely at the definition of $EXP$ (which again, you can find in The Zoo), and then show that $L$ satisfies all the requirements. Also, $BPP$ is a class of languages, not of machines. Consider for example the complexity class $Sparse$, which consists of all languages that have a certain density, but which are not necessarily computable by any Turing Machine; the definition is not at all tied to the notion of computation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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