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


Your Answer

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

Browse other questions tagged or ask your own question.