MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Context

In the work of Baker, Gill, Solovay, we know that there exists some oracle A s.t.

$$P^A = NP^A$$.

Now, in CCAMA, this oracle $A$ is given as an EXP complete language.

## Question:

Can we do this with something weaker? Say a PSPACE-complete language, like quantified boolean formulas? Intuitively, it seems that if we have the power of the polynomial hierarchy, all what $NP^{PSPACE}$ really does is add an extra layer of quantifiers, which thus is contained in $PSPACE$, and contained in $P^{PSPACE}$.

Thanks!

-
yes, you can. In fact other books take the oracle to be TQBF. (I don't have the book here but I think you might be confusing this the complexity of oracle B which separates them). – Kaveh Jun 25 at 22:36
ps: IMHO this seems more suitable for MSE(math.stackexchange.com) / CS.SE(cs.stackexchange.com) – Kaveh Jun 25 at 22:37
Kaveh, I would encourage you simply to post an answer to the question if you are able to do so. It seems to be a fine question. – Joel David Hamkins Jun 25 at 22:49

There is an oracle $A$ s.t. $\mathsf{P}^A = \mathsf{NP}^A$. The oracle normally used for the theorem is the set TQBF which is a $\mathsf{PSpace\text{-}complete}$ set.

$\mathsf{PSpace} \subseteq \mathsf{P}^\mathsf{TQBF} \subseteq \mathsf{NP}^\mathsf{TQBF} \subseteq \mathsf{PSpace}^\mathsf{TQBF} \subseteq \mathsf{PSpace}$

All inclusions are clear, the last one follows from the fact that TQBF is in $\mathsf{PSpace}$ and you can replace the oracle for TQBF with the $\mathsf{PSpace}$ machine solving it and the resulting machine will be in $\mathsf{PSpace}$.

-
 Very nice, thanks! – unknown (google) Jul 18 at 3:20