<p>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}}$.</p>

<p>Is there such a result in the literature indeed?</p>

CC BY-SA 3.0
2015-02-09T06:45:10.400Z
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
CC BY-SA 3.0
2015-02-09T16:55:39.490Z
Lance Fortnow does know the reference :) http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html
Alessandro Cosentino
CC BY-SA 3.0
2015-02-09T22:48:57.820Z
@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
CC BY-SA 3.0
2015-02-10T13:22:25.407Z
Heller is the first http://dx.doi.org/10.1016/S0019-9958(86)80012-2
Lance Fortnow
CC BY-SA 3.0
2015-02-10T18:42:39.083Z
I went back to the blog entry and replaced the links with DOIs that should last forever.
Lance Fortnow
CC BY-SA 4.0
2021-08-01T20:22:41.283Z
@Alessandro care to post as an answer?
Joshua Grochow
<cc.complexity-theory><reference-request><oracles><relativization>
An oracle relative to which EXP(NP) = BPP
Pteromys
# An oracle relative to which EXP(NP) = BPP

(Asked by: username_0 on 2015-02-09)

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?

**Tags:** cc.complexity-theory, reference-request, oracles, relativization
> **Comments:**
> **username_1**: 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.  
> **username_2**: Lance Fortnow does know the reference :) http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html  
> **username_0**: @AlessandroCosentino The link on Fortnow's blog is dead.  I would accept your answer if you could provide me with more concrete bibliographic information.  
> **username_3**: Heller is the first http://dx.doi.org/10.1016/S0019-9958(86)80012-2  
> **username_3**: I went back to the blog entry and replaced the links with DOIs that should last forever.  
> **username_4**: @Alessandro care to post as an answer?  

---

## 0 answers

