# Class Separation, Oracles, Relativization

It is known, there exists oracles A, B s.t.:

$P^A = NP^A; P^B \neq NP^B$, showing that any proof of P vs NP must be non-relativizing.

Questions:

(1) Can we actually use Oracles to separate complexity classes? I.e. are there classes X, Y, s.t. some oracle C is instrumental in separating X & Y?

(2) If complexity classes X,Y satisfy existence of oracles A,B s.t. $X^A = Y^A ; X^B \neq Y^B$ ... then it means any proof separating X,Y can't be relativizing -- but does it mean oracles can't be used to separate the classes?

Thanks!

• I recommend changing the title to remove the things in brackets. Instead, add the appropriate tags. Mar 12 '11 at 6:23
• oracles and relativizations are not means for proving separations. Do you mean diagonalization? Aug 15 '12 at 4:03

Here's an example: the polynomial hierarchy is infinite if and only if it is infinite relative to some (equivalently, any) sparse oracle. Similarly for $PH$ vs $PSPACE$. See, for example:
On the other hand, I'm not sure I know of any examples of classes where $X = Y$ if and only if $X^A = Y^A$ for some (or every) oracle $A$.
It's also probably worth mentioning that the separation $PARITY \notin AC_0$ was realized by constructing an oracle relative to which $PH$ is infinite (Furst-Saxe-Sipser). There is often a close connection between oracle constructions and (exponentially smaller) circuit lower bounds, but I think this isn't quite what you had in mind by "using an oracle to separate complexity classes."
• $X=Y$ implies $X^A=Y^A$ when $X,Y$ are “small” complexity classes like $\mathrm{AC}^0[m]$, $\mathrm{TC}^0$, $\mathrm{NC}^1$. See rd.springer.com/chapter/10.1007/978-3-540-74915-8_29 . Aug 7 '12 at 10:37