5
$\begingroup$

Is it known if $\mathsf{P}^\mathsf{BPP}= \mathsf{BPP}$ ?

It's clear that $\mathsf{BPP} \subseteq \mathsf{P}^\mathsf{BPP}$. Now, since $\mathsf{BPP}$ is closed under complementation, union, and intersection, it seems to provide evidence that $\mathsf{BPP} = \mathsf{P}^\mathsf{BPP}$. However, I can't prove this.

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ Is it well defined what it means to have a randomized complexity class (with no complete problems) as an oracle ? $\endgroup$
    – Suresh Venkat
    Jan 1 '13 at 18:31
  • 4
    $\begingroup$ Suresh: $P^{\mathcal C}$ is well defined for any set of languages $\mathcal{C}$. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 1 '13 at 18:42
  • 7
    $\begingroup$ Can't you trivially simulate each BPP oracle call within your polynomial-time randomized algorithm? You'll just need to improve the error probability of each such simulation to, say, exponentially small so that the total chance of making an error throughout the algorithm stays small enough. $\endgroup$
    – Mahdi Cheraghchi
    Jan 1 '13 at 20:22
  • 3
    $\begingroup$ @Kristoffer would you mind giving the formal definition or confirming if the following is correct? "$P^{BPP}$ is the set of languages decidable in polytime by a deterministic TM with access to a yes/no oracle for some language in $BPP$." $\endgroup$
    – usul
    Jan 1 '13 at 20:26
  • 2
    $\begingroup$ @SureshVenkat: The motivation came from looking at oracle separation results and wondering ... what is the power of a BPP oracle? We know that P^P = P, we also know that P^NP probably != NP, probably != coNP; but for BPP, it's not clear at all to me how powerful it is as an oracle. I'll be sure to add more "motivation" in the future. $\endgroup$
    – user13175
    Jan 2 '13 at 17:19
6
$\begingroup$

Yes, since BPP is low, but this is not a research level question.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ But it would come under the category of "things that are well known in one subcommunity but not in another" $\endgroup$
    – Suresh Venkat
    Jan 2 '13 at 17:43
  • $\begingroup$ I am sure you know these things better than me, but statements like this can be verified with 5 mins googling, imo. $\endgroup$
    – domotorp
    Jan 2 '13 at 17:45
  • 1
    $\begingroup$ I agree, once you understand that this notion is linked to the notion of "lowness". but that's probably what the OP was looking for. $\endgroup$
    – Suresh Venkat
    Jan 2 '13 at 17:50
  • 2
    $\begingroup$ @domotorp: Having just read the proof cs.rutgers.edu/~allender/538/murata3.pdf (linked from your wikipedia article), I do admit: my question was not research level. $\endgroup$
    – user13175
    Jan 2 '13 at 17:50

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.