MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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


share|cite|improve this question
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( / CS.SE( – 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
up vote 5 down vote accepted

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

share|cite|improve this answer
Very nice, thanks! – user22209 Jul 18 '12 at 3:20
Can you explain this more analytically? PSpace⊆PTQBF⊆NPTQBF⊆PSpaceTQBF⊆PSpace – user40215 Sep 19 '13 at 15:27
@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. – Kaveh Sep 19 '13 at 19:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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