<p>The oracle goes back to <a href="http://dx.doi.org/10.1145/800061.808740" rel="nofollow">Stockmeyer</a> in 1983. <a href="http://dx.doi.org/10.1016/S0019-9958%2886%2980012-2" rel="nofollow">Heller</a> gave the stronger result that : $BPP = EXP^{NP}$ in a relativized world in 1986. <a href="http://www.springerlink.com/content/72u535t135323r2n/" rel="nofollow">Karpiniski and Verbeek</a> (mentioned in the comments) reprove Heller's result.</p>

CC BY-SA 3.0
2011-11-16T21:02:40.697Z
Thank you for nailing it down.  I will wait for one day or two and then accept unless anything surprising happens.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-17T01:03:27.577Z
it would be nice if someone updates the entry in the complexity zoo. I could do it, but I don't know how.
Marcos Villagra
CC BY-SA 3.0
2011-11-17T16:32:54.363Z
@MarcosVillagra maybe just email Greg Kuperberg ?
Suresh Venkat
CC BY-SA 3.0
2011-11-17T18:39:01.987Z
@SureshVenkat If you mean the Complexity Zoology, unfortunately that's not a public wiki. If you mean the Complexity Zoo, then I've already updated it.
Alessandro Cosentino
CC BY-SA 3.0
2011-11-16T20:48:45.603Z
2012-01-10T12:10:25.803Z
2012-01-10T12:10:25.803Z
Lance Fortnow
<p><a href="http://www.math.ucdavis.edu/~greg/zoology/relations.html#bpp" rel="nofollow noreferrer">Complexity Zoology</a> by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X}$ — but does not give a reference for this result.  Why does this hold?  Or where can a proof be found?</p>

<p>This question is partly motivated by <a href="https://cstheory.stackexchange.com/questions/8297/what-is-known-about-multi-prover-interactive-proofs-with-short-messages/8429#8429">my answer</a> to the question “What is known about multi-prover interactive proofs with short messages?” by Joe Fitzsimons.</p>

<p>I posted this question on <a href="https://math.stackexchange.com/questions/69318/oracle-relative-to-which-bpp-is-not-contained-in-2p">math.stackexchange.com</a> on October 2, but I did not receive any answer and deleted the question on math following <a href="http://meta.math.stackexchange.com/questions/1733/what-is-the-proper-way-to-acknowledge-an-answer-posted-on-another-forum-site/1735#1735">this post</a> on meta.math.</p>

CC BY-SA 3.0
2011-11-16T19:24:46.187Z
maybe this helps? http://www.icsi.berkeley.edu/pubs/techreports/tr-92-078.pdf
Alessandro Cosentino
CC BY-SA 3.0
2011-11-16T19:26:06.327Z
@Alessandro: Thanks, it seems very relevant.  I will check it.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-17T03:11:54.683Z
the link to the Complexity Zoo entry got lost in the editing of the answer. Here it is, updated after @MarcosVillagra request: http://qwiki.stanford.edu/index.php/Complexity_Zoo:D#delta2p
Alessandro Cosentino
<cc.complexity-theory><oracles><relativization><polynomial-hierarchy><separation>
Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$
Tsuyoshi Ito
# Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

(Asked by: username_0 on 2011-11-16)

[Complexity Zoology](http://www.math.ucdavis.edu/~greg/zoology/relations.html#bpp) by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta\_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X}$ — but does not give a reference for this result. Why does this hold? Or where can a proof be found?

This question is partly motivated by [my answer](https://cstheory.stackexchange.com/questions/8297/what-is-known-about-multi-prover-interactive-proofs-with-short-messages/8429#8429) to the question “What is known about multi-prover interactive proofs with short messages?” by Joe Fitzsimons.

I posted this question on [math.stackexchange.com](https://math.stackexchange.com/questions/69318/oracle-relative-to-which-bpp-is-not-contained-in-2p) on October 2, but I did not receive any answer and deleted the question on math following [this post](http://meta.math.stackexchange.com/questions/1733/what-is-the-proper-way-to-acknowledge-an-answer-posted-on-another-forum-site/1735#1735) on meta.math.

**Tags:** cc.complexity-theory, oracles, relativization, polynomial-hierarchy, separation
> **Comments:**
> **username_1**: maybe this helps? http://www.icsi.berkeley.edu/pubs/techreports/tr-92-078.pdf  
> **username_0**: @Alessandro: Thanks, it seems very relevant.  I will check it.  
> **username_1**: the link to the Complexity Zoo entry got lost in the editing of the answer. Here it is, updated after @MarcosVillagra request: http://qwiki.stanford.edu/index.php/Complexity_Zoo:D#delta2p  

---

## 1 answers

### Answer by username_2 on 2011-11-16. Score: 18 | Accepted answer

The oracle goes back to [Stockmeyer](http://dx.doi.org/10.1145/800061.808740) in 1983. [Heller](http://dx.doi.org/10.1016/S0019-9958%2886%2980012-2) gave the stronger result that : $BPP = EXP^{NP}$ in a relativized world in 1986. [Karpiniski and Verbeek](http://www.springerlink.com/content/72u535t135323r2n/) (mentioned in the comments) reprove Heller's result.

> **Comments:**
> **username_0**: Thank you for nailing it down.  I will wait for one day or two and then accept unless anything surprising happens.  
> **username_3**: it would be nice if someone updates the entry in the complexity zoo. I could do it, but I don't know how.  
> **username_4**: @MarcosVillagra maybe just email Greg Kuperberg ?  
> **username_1**: @SureshVenkat If you mean the Complexity Zoology, unfortunately that's not a public wiki. If you mean the Complexity Zoo, then I've already updated it.  

---

