3
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I recommend changing the title to remove the things in brackets. Instead, add the appropriate tags. $\endgroup$
    – Sean Tilson
    Commented Mar 12, 2011 at 6:23
  • $\begingroup$ oracles and relativizations are not means for proving separations. Do you mean diagonalization? $\endgroup$
    – Kaveh
    Commented Aug 15, 2012 at 4:03

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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$
    – Emil Jeřábek
    Commented Aug 7, 2012 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$
    – Joshua Grochow
    Commented Aug 7, 2012 at 18:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .