most recent 30 from http://mathoverflow.net 2013-05-20T15:51:07Z http://mathoverflow.net/feeds/question/76109 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76109/oracle-separation-results-ao-bo-yet-a-b oracles 2011-09-22T08:07:57Z 2011-09-22T09:00:28Z

<p>I know that there exists classes $A$ and $B$ such that:</p> <p>$A^{O_1} = B^{O_1}$, $A^{O_2} != B^{O_2}$.</p> <p>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$?</p>

http://mathoverflow.net/questions/76109/oracle-separation-results-ao-bo-yet-a-b/76114#76114 wood 2011-09-22T09:00:28Z 2011-09-22T09:00:28Z

<p>In short the answer is YES.</p> <p>I believe the first example was the proof that $IP=PSPACE$. See <a href="http://en.wikipedia.org/wiki/IP_%28complexity%29" rel="nofollow">http://en.wikipedia.org/wiki/IP_%28complexity%29</a> for the proof.</p> <p>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</p>