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.


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


  • 1
    $\begingroup$ 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). $\endgroup$
    – Kaveh
    Jun 25 '12 at 22:36
  • 1
    $\begingroup$ ps: IMHO this seems more suitable for MSE(math.stackexchange.com) / CS.SE(cs.stackexchange.com) $\endgroup$
    – Kaveh
    Jun 25 '12 at 22:37
  • $\begingroup$ 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. $\endgroup$ Jun 25 '12 at 22:49
  • $\begingroup$ CCAMA is reference to....? $\endgroup$
    – Mr.
    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}$.

  • $\begingroup$ Can you explain this more analytically? PSpace⊆PTQBF⊆NPTQBF⊆PSpaceTQBF⊆PSpace $\endgroup$
    – user40215
    Sep 19 '13 at 15:27
  • 2
    $\begingroup$ @user40215, I don't think that is suitable on MO, this is standard undergraduate material. If you have trouble understanding it you can post a question about the part you don't understand on Computer Science. $\endgroup$
    – Kaveh
    Sep 19 '13 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.