# Why 0-BPP equals P

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.

• Thanks alot. The point I was missing was "for all distributions". – 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.

• 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). – Ariel May 5 '17 at 16:12