Has Oracles actually provided intuition for proving anything in Complexity Theory? - MathOverflow

Has Oracles actually provided intuition for proving anything in Complexity Theory?

2011-09-27T14:04:27Z

[EDIT: I realize this question is soft. I realize some people want to close this question. The goal here is trying to answer the following question:

So I see these research papers that provide papers for oracles B s.t. C^B != D^B.

Question: How do I build on these results? [Besides proving other oracles?] Are there examples where people have techniques that utilize oracle separations? ]

Known:

For many classes C, D we do not know about C vs D, but we have oracles relative to which C^A = D^A, C^B != D^B.

Question:

Is there any class separation result that has been inspired by Oracles? I.e. the argument is that finding such oracles shows that these classes are "hard to separate", -- but does having examples of separating oracles actually help separate the class?

Is there any case where the existence of a B s.t. C^B != D^B somehow guided the proof of C != D ?

Thanks!

Answer by Aaron Sterling for Has Oracles actually provided intuition for proving anything in Complexity Theory?

2011-09-27T17:50:04Z

There are probably several excellent answers to your question, but I will give you my own mediocre one.

The existence of an oracle separation means, "Nonrelativizing techniques are needed to prove something here." As there are few nonrelativizing techniques, it either tells exactly which tools to use, or tells that brand new techniques are probably needed, so pursuing work in this direction is likely to be hard. This has caused complexity theorists to open new areas of research, to be able to say something about questions whose direct answer appears very hard to obtain.

See The Role of Relativization in Complexity Theory by Fortnow for much more.

Answer by Kaveh for Has Oracles actually provided intuition for proving anything in Complexity Theory?

2011-09-27T21:21:40Z

IIRC, the circuit complexity classes like $\mathsf{AC^0}$ were studied originally for proving relativization results. A classical example is Furst, Saxe, and Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy".