3

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$?

flag

1 Answer

9

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

link|flag

Your Answer

Get an OpenID
or

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