Oracle Results: P^A = NP^A

2012-06-25T22:19:13Z

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!

Answer by Kaveh for Oracle Results: P^A = NP^A

2012-06-26T03:41:24Z

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

Oracle Results: P^A = NP^A - MathOverflow

Oracle Results: P^A = NP^A

Context

Question:

Answer by Kaveh for Oracle Results: P^A = NP^A