# Oracle Results: P^A = NP^A

## 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 '12 at 22:36
ps: IMHO this seems more suitable for MSE(math.stackexchange.com) / CS.SE(cs.stackexchange.com) –  Kaveh Jun 25 '12 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 '12 at 22:49
CCAMA is reference to....? –  Turbo Sep 19 '13 at 19:05

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