Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$?

Question

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$?

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, Jan 11 '15 at 13:20

score 1 · Accepted Answer · answered Jan 11 '15 at 13:24

1

Yes, the Baker-Gill-Solovay B oracle is itself in EXP.

answered Jan 11 '15 at 13:24

http://zoo.cs.yale.edu/classes/cs468/BGS.pdf – Jan 11 '15 at 13:25
1

http://cstheory.stackexchange.com/questions/21663/baker-gill-solovay-pb-ne-npb-relativization-what-class-is-b-in – Jan 11 '15 at 13:25

1 Answers1