# An oracle relative to which EXP(NP) = BPP

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?

• 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. – Ryan Williams Feb 9 '15 at 6:45
• Lance Fortnow does know the reference :) blog.computationalcomplexity.org/2005/08/extreme-oracles.html – Alessandro Cosentino Feb 9 '15 at 16:55
• @AlessandroCosentino The link on Fortnow's blog is dead. I would accept your answer if you could provide me with more concrete bibliographic information. – Pteromys Feb 9 '15 at 22:48
• Heller is the first dx.doi.org/10.1016/S0019-9958(86)80012-2 – Lance Fortnow Feb 10 '15 at 13:22
• I went back to the blog entry and replaced the links with DOIs that should last forever. – Lance Fortnow Feb 10 '15 at 18:42