10
$\begingroup$

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).

Improve this question
$\endgroup$
4
  • $\begingroup$ What exactly do you mean by p being (un)computable? $\endgroup$
    – daniello
    Commented Aug 7, 2016 at 19:48
  • $\begingroup$ I added the definition of $BPP$-computable. For computable in general one may just drop the words "randomized polynomial" or simply say that binary expansion is computable. (With bounded resources this is not the same.) $\endgroup$
    – Daniil Musatov
    Commented Aug 8, 2016 at 1:42
  • $\begingroup$ I think $BPP_p \neq BPP$ for every uncomputable $p$ because given a $p$-biased coin one can compute the $n$'th bit of $p$ by sampling. Suppose we can compute the $n$'th bit in time $f(n)$, then the language that contains $1^x$ for all $x$ such that the $f^{-1}(x)$'th bit of $p$ is $1$ is in $BPP_p$, but clearly it is uncomputable. $\endgroup$
    – daniello
    Commented Aug 8, 2016 at 2:45
  • $\begingroup$ This is definitely true for vast majority of uncomputable $p$. But there is a caveat: if $p$ contains very long sequences of zeros and ones then it may need very long sampling to determine the $n$'th bit. This sampling may be so long that $f(n)$ would be uncomputable (like the Busy Beavers function). I also doubt it can be precisely computed from sampling itself. And it seems that without computing $f(n)$ one cannot recognize the language mentioned. $\endgroup$
    – Daniil Musatov
    Commented Aug 8, 2016 at 4:16

1 Answer 1

Reset to default
1
$\begingroup$

1) Yes, but only because of your definition. Take a unary language $L\in EXP\setminus BPP$ (yeah, I know this might be empty, in that case just take something even bigger than $EXP$), that is very sparse in the sense that $n\notin L$ if $n$ is not a tower of $2's$, i.e., of the form $2^{2^{2^\ldots}}$. Define $p=\sum_{n\in L} 1/n$. This $p$ is not $BPP$-computable, but $p$ can be approximated in $P$ up to a small enough additive error that allows the simulation of a $BPP_p$ machine.

Had you defined $BPP$-computable such that you want to approximate $p$ up to an additive error of $1/n$ (instead of $1/2^n$) in polynomial time, things would be different.

Update. The below answer is for the case when the additive error we allow is $2^{-n}$ instead of $2^{-n-1}$.

2) Yes, because here you can forget about the polynomial restriction on the classes and by sampling $2^n$ times you can get the $n$-th bit of $p$ in $BPP_p$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 2) I think that central limit theorem suggests that one should sample $2^{2n}$, not $2^n$, times to acquire $2^{-n}$ precision. But the main problem is that sometimes we need much greater precision. Say, if $|p-\frac12|<\epsilon$ then one needs $\frac1{\epsilon^2}$ samples to compute even the first digit. And the number of samples needed may be arbitrarily, even uncomputably, large. The point is a bit clarified in the edit. $\endgroup$
    – Daniil Musatov
    Commented Aug 8, 2016 at 6:08
  • $\begingroup$ @Daniil: As I've commented on the question as well, you did not ask for the computation of the digits in your definition of $BPP$-computable. So, if $p$ equals, say, $0.01111111111$, then one should guess $1$ for the first digit after the comma according to your def. $\endgroup$
    – domotorp
    Commented Aug 8, 2016 at 7:00
  • $\begingroup$ We are now talking about uncomputable $p$, aren't we? If I understand you right, you suggest not to compute by sampling digits of $p$, but instead to compute whether the $i$'th digit of $2^{-i-1}$ binary rational approximation of $p$ is 1. But here we face the same problem: to compute the first digit we need to distinguish 0.010000000001 and 0.001111111110. $\endgroup$
    – Daniil Musatov
    Commented Aug 8, 2016 at 11:53
  • $\begingroup$ @Daniil: OK, my bad, I thought you wanted a binary rational whose distance is at most $2^{-n}$ from $p$. I have updated my answer accordingly. Are you happy with my solution to 1)? $\endgroup$
    – domotorp
    Commented Aug 8, 2016 at 20:11

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.