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?


  • 1
    $\begingroup$ I recommend changing the title to remove the things in brackets. Instead, add the appropriate tags. $\endgroup$ Mar 12 '11 at 6:23
  • $\begingroup$ oracles and relativizations are not means for proving separations. Do you mean diagonalization? $\endgroup$
    – 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."

  • 2
    $\begingroup$ $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 . $\endgroup$ Aug 7 '12 at 10:37
  • $\begingroup$ @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.) $\endgroup$ Aug 7 '12 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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