Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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. –  Kaveh Jan 22 '13 at 3:46
    
I see, so if it was a constant it was in $\sf BPP$ but since it is not, we can't tell? –  Jozef Jan 22 '13 at 11:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.