1
$\begingroup$

I know that $\sf BPP[2/3,1/3]= BPP[\alpha,\beta]$ when $\alpha\lt\beta$, but I read something on Wikipedia which got me confused:

In practice, an error probability of $1/3$ might not be acceptable, however, the choice of $1/3$ in the definition is arbitrary. It can be any constant between $0$ and $1/2$ (exclusive) and the set $\mathsf{BPP}$ will be unchanged.

The reason for my question is the this question that I'm trying to answer:

We define the class $PP_{\frac{7}{8}}$: $L \in PP_{\frac{7}{8}}$. There's a probabilistic Turing machine that for $x \in L$ accepts $x$ with probability $>$ than $\frac{7}{8}$ and for $x \notin L$ it accepts $x$ with probabilty $\leq \frac{7}{8}$.

So by the $\alpha, \beta$ first definition I can conclude that $PP_{\frac{7}{8}}$ which equals to $\sf BPP[7/8,7/8+\epsilon]$ also equals to $\sf BPP[2/3,1/3]$ but the I am asked to prove that $\sf NP \subseteq BPP$ which we don't know yet.

$\endgroup$

1 Answer 1

3
$\begingroup$

For what value of $\epsilon$ does PP$_{7/8}$ equal BPP$[7/8,7/8+\epsilon]$? All you're given is that if $x \in L$ then the probability is strictly larger than $7/8$, while if $x \notin L$ then the probability is at most $7/8$. It could be that when $x \in L$, the machine accepts with probability $7/8 + 2^{-n}$. In fact, PP contains NP, while BPP is conjectured (by some) to equal P.

$\endgroup$
2
  • $\begingroup$ Adding to what Yuval wrote, the important distinction between BPP and PP is the gap between accept and reject probabilities. In PP there is no gap. In BPP there is non-negligible between the accept and reject. $\endgroup$
    – Kaveh
    Commented Jan 22, 2013 at 3:46
  • $\begingroup$ I see, so if it was a constant it was in $\sf BPP$ but since it is not, we can't tell? $\endgroup$
    – Jozef
    Commented Jan 22, 2013 at 11:07

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.