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$
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$
  • $\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 Jan 22 '13 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 Jan 22 '13 at 11:07

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.