HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is 0-BPP equal to P

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
equalwhybpp

Problem

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?

Solution

$\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.

Context

StackExchange Computer Science Q#74958, answer score: 4

Revisions (0)

No revisions yet.