Sorry if it is an obvious question, since all my searches lead to "clearly 0-BPP=P" (like Papadimitriou text book or Complexity Zoo). I understand that any P machine can be seen as a 0-BPP machine with a 0-assignment function that assigns exactly 0 or 1 to any non deterministic choice, which makes P a subset of 0-BPP. But what about the converse?


$\delta-\mathsf{BPP}$ is the set of all languages $L$ such that there exists a polynomial Turing machine $M(x,r)$, and some polynomial $p(n)$ such that:

$\forall x\in\Sigma^* : \Pr\limits_{r\sim\mathcal{D}_\delta\left(\{0,1\}^{p(n)}\right)}\left[M(x,r)=L(x)\right]\ge\frac{2}{3}$

For all $\delta$-semi random distributions $D_\delta$ on strings $\{0,1\}^{p(n)}$. $D_\delta$ is said to be $\delta$ semi random if $\Pr\left[x_i = 1 | x_1,...,x_{i-1}\right]\in\left[\delta,1-\delta\right]$.

Note that $M$ is guaranteed to agree with $L$ with probability $\ge\frac{2}{3}$ for all distributions $D_\delta$ which are $\delta$ semi random (meaning that $M$ can handle "adversarial distributions").

If $\delta=0$, you have a complete freedom in the choice $D_\delta$, so you can choose the deterministic one which always outputs 0, and you are guaranteed that $M$ knows how to handle it and still agrees with $L$ with high probability. However, if the distribution is fixed at 0, $M$ accepts any input with probability $1$ or $0$, hence it always outputs the correct answer.

  • $\begingroup$ Thanks alot. The point I was missing was "for all distributions". $\endgroup$ – Beleg May 6 '17 at 6:14

It's a polynomial-time Turing machine with access to "random" bits that are guaranteed to have value zero. Since the random bits are completely deterministic, the machine is just a deterministic polynomial-time TM.

  • 1
    $\begingroup$ It's a polynomial time Turing machine that can "work" with any given distribution (not just the deterministic ones). Its your job to feed it with a fixed distribution, so I wouldn't say it has access to bits who are guaranteed to have value zero (as it could also work with the uniform distribution). $\endgroup$ – Ariel May 5 '17 at 16:12

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.