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