Oracle Separation Results: A^O != B^O yet A = B ? - MathOverflow 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 Oracle Separation Results: A^O != B^O 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 Answer by wood for Oracle Separation Results: A^O != B^O yet A = B ? 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>