# 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. – Sean Tilson Mar 12 '11 at 6:23
@Sean: Thanks! Done. – LowerBounds Mar 14 '11 at 18:53
oracles and relativizations are not means for proving separations. Do you mean diagonalization? – Kaveh 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:

Balcázar, J. L., Book, R. V. and Schöning, U. The polynomial-time hierarchy and sparse oracles. J. ACM 1986.

Now, it's not clear how having the sparse oracle helps you come up with a proof of one of these statements, but at least we know you can use it if it helps.

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 . – Emil Jeřábek Aug 7 '12 at 10:37
@Emil: Interesting! (It is striking, however, that these seem to be the only examples of such a phenomenon, and the classes are "so small" that even defining a good notion of relativization for them took a long time.) – Joshua Grochow Aug 7 '12 at 18:01