<p>According to Baker, Gill, Solovey where is an oracle A in EXP, so $P^A$ = $NP^A$. But is there an oracle B in EXP, what $P^B$ $\ne$ $NP^B$?</p>

CC BY-SA 3.0
2015-01-11T10:45:22.027Z
Never mind, I was mistaken.
Tom van der Zanden
CC BY-SA 3.0
2015-01-11T13:20:53.020Z
Yes. Such an oracle $B$ can be constructed by running an exponential number of steps of a polynomial number of Turing machines. So indeed it can be chosen in EXP. A lot of resources on that can be found on the web.
Nicolas Perrin
<p-vs-np>
Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$?
Ava_Katushka
# Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$?

(Asked by: username_0 on 2015-01-11)

According to Baker, Gill, Solovey where is an oracle A in EXP, so $P^A$ = $NP^A$. But is there an oracle B in EXP, what $P^B$ $\ne$ $NP^B$?

**Tags:** p-vs-np

> **Comments:**
> **username_1**: Never mind, I was mistaken.  
> **username_2**: Yes. Such an oracle $B$ can be constructed by running an exponential number of steps of a polynomial number of Turing machines. So indeed it can be chosen in EXP. A lot of resources on that can be found on the web.  

---

## 0 answers

