Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.


(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?


share|improve this question
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
add comment

1 Answer

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."

share|improve this answer
$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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.