5
$\begingroup$

The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the classes. (For example, this lecture describes one particular oracle separation as "formal evidence" that the complexity classes are unconditionally distinct.) However, as far as I understand (please correct me if I am wrong), for complexity classes $A$ and $B$ and an oracle for a language $L$, all four of these cases are logically possible:

  1. $A = B$ and $A^L = B^L$
  2. $A = B$ and $A^L \neq B^L$
  3. $A \neq B$ and $A^L = B^L$
  4. $A \neq B$ and $A^L \neq B^L$

So presuming that at the end of the day the unrelativized result is what we really care about, what are relativized results "good for"?

I can see one application: if we happen to be able to find oracles for two languages $L$ and $L'$ such that $A^L = B^L$ and $A^{L'} \neq B^{L'}$, then that tells us that any proof that either $A = B$ or $A \neq B$ cannot relativize, and this fact saves us a lot of time by allowing us to immediately skip many potential proofs.

But do oracle results give us any evidence about the actual relation? In particular, why are oracle separations treated as "evidence" (though not a proof) that the complexity classes are unequal? How strong does the complexity-theory community consider such evidence to be? (I know that last question is subjective and hard to answer precisely.)

$\endgroup$
0
3
+25
$\begingroup$

I am by no means an expert, but 2 things come to mind:

  1. Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the techniques used for such a proof, and thus it is helpful in the way towards getting a proof.

  2. Because if you prove $A^L = B^L$, and the oracle is not very strong, then it seems that you are narrowing down the possibility of $A \neq B$, as with some extra help they become equal. This can arguably be evidence towards believing that $A = B$. To me it feels like saying that John and Peter were equally strong in a fight with boxing gloves. That doesn't necesarily mean that they will be equally strong without the gloves, as one of them could be weaker but use the gloves better. Nevertheless, the information about their fight with gloves is arguable evidence of their relative strength.

$\endgroup$
2
  • $\begingroup$ Thank you Bernardo! What do you mean by "oracle is not very strong"? Or can you classify what is oracle strong, and what is not? $\endgroup$ – user777 May 17 at 3:56
  • 1
    $\begingroup$ It depends on the context. But for example, PSPACE is very strong with respect to P and NP, and thus $\mathrm{P}^\mathrm{PSPACE} =\mathrm{NP}^\mathrm{PSPACE}$. This is like saying that I'm equally strong as Mike Tyson, if we are both equipped with a Bazooka... $\endgroup$ – Bernardo Subercaseaux Jun 11 at 19:55

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.