<p>Yes, since BPP is <a href="http://en.wikipedia.org/wiki/Low_%28complexity%29">low</a>, but this is not a research level question.</p>

CC BY-SA 3.0
2013-01-02T17:43:44.727Z
But it would come under the category of "things that are well known in one subcommunity but not in another"
Suresh Venkat
CC BY-SA 3.0
2013-01-02T17:45:19.340Z
I am sure you know these things better than me, but statements like this can be verified with 5 mins googling, imo.
domotorp
CC BY-SA 3.0
2013-01-02T17:50:11.120Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-01-02T17:42:17.210Z
2013-01-02T17:42:17.210Z
domotorp
<blockquote>
  <p>Is it known if $\mathsf{P}^\mathsf{BPP}= \mathsf{BPP}$ ?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2013-01-01T18:31:18.900Z
Is it well defined what it means to have a randomized complexity class (with no complete problems) as an oracle ?
Suresh Venkat
CC BY-SA 3.0
2013-01-01T18:42:35.720Z
Suresh: $P^{\mathcal C}$ is well defined for any set of languages $\mathcal{C}$.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-01T20:22:20.743Z
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.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-01-01T20:26:05.193Z
@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$."
usul
CC BY-SA 3.0
2013-01-02T12:40:16.713Z
usul: Your statement is correct.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-02T16:47:44.247Z
It was my mistake. I should have tagged it "relativized" rather than "advice". As for the down vote, I'm not sure. It seems reasonable to me. But with questions like this, it often helps if you can provide some motivation as to why you're asking
Suresh Venkat
CC BY-SA 3.0
2013-01-02T18:36:31.610Z
The down-votes are probably because the question looks like a homework which would make it off-topic. Please check the [faq]. As Suresh wrote stating the motivation inside the post would make it clear the question is on-tipic and would help with avoiding down-votes. (Using a real name would also help.)
Kaveh
CC BY-SA 3.0
2013-01-02T18:51:27.477Z
PS: I think this is off-topic. The answer is as MCH wrote (i.e. no need to know about lowness).
Kaveh
<cc.complexity-theory><oracles>
$\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal)
lazy
# $\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal)

(Asked by: username_0 on 2013-01-01)

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

**Tags:** cc.complexity-theory, oracles
> **Comments:**
> **username_1**: Is it well defined what it means to have a randomized complexity class (with no complete problems) as an oracle ?  
> **username_2**: Suresh: $P^{\mathcal C}$ is well defined for any set of languages $\mathcal{C}$.  
> **username_3**: 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.  
> **username_4**: @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$."  
> **username_2**: usul: Your statement is correct.  
> **username_1**: It was my mistake. I should have tagged it "relativized" rather than "advice". As for the down vote, I'm not sure. It seems reasonable to me. But with questions like this, it often helps if you can provide some motivation as to why you're asking  
> **username_5**: The down-votes are probably because the question looks like a homework which would make it off-topic. Please check the [faq]. As Suresh wrote stating the motivation inside the post would make it clear the question is on-tipic and would help with avoiding down-votes. (Using a real name would also help.)  
> **username_5**: PS: I think this is off-topic. The answer is as MCH wrote (i.e. no need to know about lowness).  

---

## 1 answers

### Answer by username_6 on 2013-01-02. Score: 6

Yes, since BPP is [low](http://en.wikipedia.org/wiki/Low_%28complexity%29), but this is not a research level question.

> **Comments:**
> **username_1**: But it would come under the category of "things that are well known in one subcommunity but not in another"  
> **username_6**: I am sure you know these things better than me, but statements like this can be verified with 5 mins googling, imo.  
> **username_1**: 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.  

---

