Take the 2-minute tour ×

I know that there exists classes $A$ and $B$ such that:

$A^{O_1} = B^{O_1}$, $A^{O_2} != B^{O_2}$.

Now, this is my question: do we know of any classes $A$ and $B$ such that $A=B$, yet there is an oracle $O$ such that $A^O != B^O$?

share|improve this question

1 Answer 1

In short the answer is YES.

I believe the first example was the proof that $IP=PSPACE$. See http://en.wikipedia.org/wiki/IP_%28complexity%29 for the proof.

But there exist oracles such that $IP^O \neq PSPACE^O$. In fact this is true for almost all oracles. See for example www.wisdom.weizmann.ac.il/~oded/PS/roh.ps

share|improve this answer

Your Answer


