# Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

Complexity Zoology 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 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 on October 2, but I did not receive any answer and deleted the question on math following this post on meta.math.

The oracle goes back to Stockmeyer in 1983. Heller gave the stronger result that : $BPP = EXP^{NP}$ in a relativized world in 1986. Karpiniski and Verbeek (mentioned in the comments) reprove Heller's result.

• Thank you for nailing it down. I will wait for one day or two and then accept unless anything surprising happens. – Tsuyoshi Ito Nov 16 '11 at 21:02
• 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 Nov 17 '11 at 1:03
• @MarcosVillagra maybe just email Greg Kuperberg ? – Suresh Venkat Nov 17 '11 at 16:32
• @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 Nov 17 '11 at 18:39