Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a machine in polynomial time. It is a standard exercise to prove that:A) If $p$ is rational or even $BPP$-computable then $BPP_p=BPP$. (By $BPP$-computable I mean: there is a randomized polynomial algorithm that being fed $n$ in unary returns w.h.p. the binary rational with denominator $2^n$ that lies within $2^{-n-1}$ of $p$.)B) For some uncomputable $p$ the class $BPP_p$ contains an undecidable language and hence is larger than $BPP$. Such values of $p$ form a dense set in $(0,1)$.My question is the following: what happens in between? Is there a criterion for $BPP_p=BPP$? In particular:1) Do uncomputable in $BPP$ probabilities $p$ exist such that $BPP_p=BPP$? (They may be computable in some higher classes).2) Is $BPP_p$ wider than $BPP$ for all uncomputable $p$? (The parameters in question are those whose binary expansion contains very long sequences of zeros and/or ones. In this case computing bits by random sampling may take very long, even uncomputable time, and the problem cannot be rescaled to polynomial time. Sometimes the difficulty can be overcome by another base of expansion, but certain $p$ may fool all bases).
When does BPP with a biased coin equal standard BPP?
cc.complexity theory;randomized algorithms;probabilistic complexity