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.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thank you for nailing it down. I will wait for one day or two and then accept unless anything surprising happens. $\endgroup$ – Tsuyoshi Ito Nov 16 '11 at 21:02
  • 4
    $\begingroup$ it would be nice if someone updates the entry in the complexity zoo. I could do it, but I don't know how. $\endgroup$ – Marcos Villagra Nov 17 '11 at 1:03
  • $\begingroup$ @MarcosVillagra maybe just email Greg Kuperberg ? $\endgroup$ – Suresh Venkat Nov 17 '11 at 16:32
  • 5
    $\begingroup$ @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. $\endgroup$ – Alessandro Cosentino Nov 17 '11 at 18:39

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.