Whether or not $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$ is an open problem, although we believe the former is strictly contained in the other. I guess, from the absence of the proof of the separation, that there should have been a relativized result on this problem, namely, the existence of an oracle relative to which $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$.

Is there such a result in the literature indeed?

  • 6
    $\begingroup$ Yes, there are oracles making them equal and oracles making them different, if I recall. Lance Fortnow knows the reference... I can try to look it up myself, but if you do a search on sciencedirect for it, you're likely to see it. $\endgroup$ – Ryan Williams Feb 9 '15 at 6:45
  • 2
    $\begingroup$ Lance Fortnow does know the reference :) blog.computationalcomplexity.org/2005/08/extreme-oracles.html $\endgroup$ – Alessandro Cosentino Feb 9 '15 at 16:55
  • $\begingroup$ @AlessandroCosentino The link on Fortnow's blog is dead. I would accept your answer if you could provide me with more concrete bibliographic information. $\endgroup$ – Pteromys Feb 9 '15 at 22:48
  • 2
    $\begingroup$ Heller is the first dx.doi.org/10.1016/S0019-9958(86)80012-2 $\endgroup$ – Lance Fortnow Feb 10 '15 at 13:22
  • 1
    $\begingroup$ I went back to the blog entry and replaced the links with DOIs that should last forever. $\endgroup$ – Lance Fortnow Feb 10 '15 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.