Problem Detail: I am confused about how PP and BPP are defined. Let us assume $chi$ is the characteristic function for a language $mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions correct:
$BPP ={mathcal{L} :Pr[chi(x) ne M(x)] geq frac{1}{2} + epsilon quad forall x in mathcal{L}, epsilon > 0 }$
$PP ={mathcal{L} :Pr[chi(x) ne M(x)] > frac{1}{2} }$ If the definition are wrong, please try to make minimal change to make them correct (i.e. do not give other equivalent definition which use counting machine or some modified model). I can not properly distinguish the conditions on probability on both the definitions. Some concrete examples with clear insight into the subtle points would be very helpful.
$BPP ={mathcal{L} :Pr[chi(x) ne M(x)] geq frac{1}{2} + epsilon quad forall x in mathcal{L}, epsilon > 0 }$
$PP ={mathcal{L} :Pr[chi(x) ne M(x)] > frac{1}{2} }$ If the definition are wrong, please try to make minimal change to make them correct (i.e. do not give other equivalent definition which use counting machine or some modified model). I can not properly distinguish the conditions on probability on both the definitions. Some concrete examples with clear insight into the subtle points would be very helpful.
Asked By : DurgaDatta
Answered By : adrianN
That looks correct to me. The difference between BPP and PP is that for BPP the probability has to be greater than $1/2$ by a constant, whereas for PP it could be $1/2+ 1/2^n$. So for BPP problems you can do probability amplification with a small number of repetitions, whereas for general PP problems you can’t.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7848
