12
$\begingroup$

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.

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Nov 16, 2011 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
    Commented Nov 17, 2011 at 1:03
  • $\begingroup$ @MarcosVillagra maybe just email Greg Kuperberg ? $\endgroup$
    – Suresh Venkat
    Commented Nov 17, 2011 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
    Commented Nov 17, 2011 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.