Oracle Results: P^A = NP^A - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:38:42Z http://mathoverflow.net/feeds/question/100637 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100637/oracle-results-pa-npa Oracle Results: P^A = NP^A unknown (google) 2012-06-25T22:19:13Z 2012-06-26T03:41:24Z <h2>Context</h2> <p>In the work of Baker, Gill, Solovay, we know that there exists some oracle A s.t.</p> <p>$$P^A = NP^A$$.</p> <p>Now, in CCAMA, this oracle $A$ is given as an EXP complete language.</p> <h2>Question:</h2> <p>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}$.</p> <p>Thanks!</p> http://mathoverflow.net/questions/100637/oracle-results-pa-npa/100658#100658 Answer by Kaveh for Oracle Results: P^A = NP^A Kaveh 2012-06-26T03:41:24Z 2012-06-26T03:41:24Z <p>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.</p> <p>$\mathsf{PSpace} \subseteq \mathsf{P}^\mathsf{TQBF} \subseteq \mathsf{NP}^\mathsf{TQBF} \subseteq \mathsf{PSpace}^\mathsf{TQBF} \subseteq \mathsf{PSpace}$</p> <p>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}$.</p>