3
$\begingroup$

[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!

$\endgroup$
1
  • 1
    $\begingroup$ If you think the question is soft, you should probably add the soft-question tag. $\endgroup$ Sep 27, 2011 at 17:56

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I think it is a very good answer, not at all a mediocre one. There is more to say on the subject, no doubt, but this must be the main remark to make here. $\endgroup$ Sep 27, 2011 at 17:59
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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