<p>We have IP = PSPACE = PPSPACE, where PPSPACE is the "probabilistic polynomial space," as defined by Papadimitriou's <a href="http://linkinghub.elsevier.com/retrieve/pii/0022000085900455" rel="noreferrer">Games Against Nature</a>.</p>

<p>However, relative to a random oracle O, we have IP<sup>O</sup> ≠ PSPACE<sup>O</sup> = PPSPACE<sup>O</sup> with probability 1. (See <a href="http://www.cs.umbc.edu/~chang/papers/roh/" rel="noreferrer">The Random Oracle Hypothesis is False</a>.)</p>

<p>Another example: let the assumption be false; that is, if A=B the A<sup>O</sup> = B<sup>O</sup> for <strong>any</strong> oracle O and <strong>all</strong> complexity classes A and B. The contrapositive will say: If A<sup>O</sup> ≠ B<sup>O</sup>, then A ≠ B. Specially, since there exists an oracle O such that P<sup>O</sup> ≠ NP<sup>O</sup>, then P ≠ N, and a long-standing problem is solved!!!</p>

<p>Obviously, this reasoning has no basis, and I believe it can be refuted as such.</p>

<p><strong>PS:</strong> When we use the "=" sign with respect to sets, we mean that every element of one set is also a member of the other set, and vice versa. However, the sets might have totally different definitions. In the axiomatic set theory, this is called the <a href="http://en.wikipedia.org/wiki/Axiom_of_extensionality" rel="noreferrer">axiom of extensionality</a>. The reason of "IP = PSPACE but IP<sup>O</sup> ≠ PSPACE<sup>O</sup> with probability 1 for a random oracle O" is exactly this: While IP and PSPACE are externally identical, their internal structure is quite different.</p>

CC BY-SA 3.0
2011-05-19T06:15:09.883Z
i.e. relativization is not defined for languages but for specific machines and depends on the structure of the machine. :)
Kaveh
CC BY-SA 3.0
2011-05-18T13:01:48.283Z
2011-05-18T13:11:26.440Z
2011-05-18T13:11:26.440Z
Sadeq Dousti
<p>We know that there exist two oracles $A$ and $B$ such that $P^A=NP^A$ and $P^B\neq NP^B$, this implies the obstacle of proving $P\neq NP$ using diagonalization.  I just wonder if there exist two complexity classes, say $A$ and $B$ and oracle $O$ such that $A=B$ but $A^O\neq B^O$?</p>

<p>I am not sure if it is a research-level problem. So don't hesitate to close it if not.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2011-05-18T12:26:21.813Z
Then it means $P\ne NP$, otherwise, how can an oracle separate them?
pyao
CC BY-SA 3.0
2011-05-18T12:27:57.927Z
OK, here "the same" means they are shown to be same, but may use completely different definitions, like $IP=PSPACE$.
pyao
CC BY-SA 3.0
2011-05-18T13:21:43.257Z
I suggest that you change the question to reflect this.
Dave Clarke
CC BY-SA 3.0
2011-05-19T06:07:56.220Z
related: [1](http://cstheory.stackexchange.com/questions/504/complexity-class-separation-in-the-presence-of-relativization-barriers)
Kaveh
<cc.complexity-theory><complexity-classes><oracles>
Is there an oracle that separates two complexity classes known to be equal?
pyao
# Is there an oracle that separates two complexity classes known to be equal?

(Asked by: username_0 on 2011-05-18)

We know that there exist two oracles $A$ and $B$ such that $P^A=NP^A$ and $P^B\neq NP^B$, this implies the obstacle of proving $P\neq NP$ using diagonalization. I just wonder if there exist two complexity classes, say $A$ and $B$ and oracle $O$ such that $A=B$ but $A^O\neq B^O$?

I am not sure if it is a research-level problem. So don't hesitate to close it if not.

Thanks.

**Tags:** cc.complexity-theory, complexity-classes, oracles

> **Comments:**
> **username_0**: Then it means $P\ne NP$, otherwise, how can an oracle separate them?  
> **username_0**: OK, here "the same" means they are shown to be same, but may use completely different definitions, like $IP=PSPACE$.  
> **username_1**: I suggest that you change the question to reflect this.  
> **username_2**: related: [1](http://cstheory.stackexchange.com/questions/504/complexity-class-separation-in-the-presence-of-relativization-barriers)  

---

## 1 answers

### Answer by username_3 on 2011-05-18. Score: 20 | Accepted answer

We have IP = PSPACE = PPSPACE, where PPSPACE is the "probabilistic polynomial space," as defined by Papadimitriou's [Games Against Nature](http://linkinghub.elsevier.com/retrieve/pii/0022000085900455).

However, relative to a random oracle O, we have IPO ≠ PSPACEO = PPSPACEO with probability 1. (See [The Random Oracle Hypothesis is False](http://www.cs.umbc.edu/~chang/papers/roh/).)

Another example: let the assumption be false; that is, if A=B the AO = BO for **any** oracle O and **all** complexity classes A and B. The contrapositive will say: If AO ≠ BO, then A ≠ B. Specially, since there exists an oracle O such that PO ≠ NPO, then P ≠ N, and a long-standing problem is solved!!!

Obviously, this reasoning has no basis, and I believe it can be refuted as such.

**PS:** When we use the "=" sign with respect to sets, we mean that every element of one set is also a member of the other set, and vice versa. However, the sets might have totally different definitions. In the axiomatic set theory, this is called the [axiom of extensionality](http://en.wikipedia.org/wiki/Axiom_of_extensionality). The reason of "IP = PSPACE but IPO ≠ PSPACEO with probability 1 for a random oracle O" is exactly this: While IP and PSPACE are externally identical, their internal structure is quite different.

> **Comments:**
> **username_2**: i.e. relativization is not defined for languages but for specific machines and depends on the structure of the machine. :)  

---

