2
$\begingroup$

If I have a proof for a separation between two complexity classes (using no oracles) and I want to see if it relativizes, how do I go about doing so?

Especially in the case where there already exist proofs for these classes being equal with respect to one oracle and not equal with respect to another oracle. I'm wondering, if I have a proof of inequality with respect to no oracle can I simply reference the oracle to which these classes have been proven equal, call on that example, and be done--since there exists an oracle to which they have already been proven equal this is my proof that the inequality doesn't relativize?

Or do I have to apply oracles specifically to the machines in my proof of the inequality and see if it relativizes?

I'm confused about how proving relativization / non-relativization of a specific proof of some statement relates to the relativization of other proofs of the same statement.

How can I reference the fact that other proofs of a statement relativize / don't relativize to help me prove my own relativization result about my proof of that statement?

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A proof relativizes if every step in the proof relativizes. You should go over your proof, and check whether each step remains valid in the presence of an oracle.

In contrast, a result relativizes by definition if it still holds relative to an arbitrary oracle. Hence, to show that a result doesn't relativize, all you have to do is give an oracle with respect to which it fails.

If we're interested in some specific statement, whose truth value we are not sure of, and there are both an oracle relative to which the statement holds and an oracle relative to which the statement doesn't hold, then we can conclude that no relativizing proof can either prove or refute the statement.

Improve this answer
$\endgroup$
11
  • $\begingroup$ So, if my result is C != B. and someone else has a result that C^O = B^O relative to O, then this is all that is needed to say that the result C=!B does not relativize, all i need to do is cite the example that C^O = B^O and this proves my result C=! B does not relativize? Or are there more steps? Sorry this is what im confused about. $\endgroup$
    – DeeDee
    Commented May 24, 2020 at 18:41
  • 2
    $\begingroup$ A proof can be relativizing, and a statement can be relativizing. If your prove a statement using a relativizing proof, then the statement is also relativizing. $\endgroup$
    – Yuval Filmus
    Commented May 25, 2020 at 15:06
  • 2
    $\begingroup$ If your proof relativizes, then what you prove also relativizes. The opposite doesn't necessarily hold. You could prove a statement that happens to relativize using a non-relativizing proof. Your proof won't show that the statement relativizes. $\endgroup$
    – Yuval Filmus
    Commented May 25, 2020 at 15:21
  • 1
    $\begingroup$ @RingRing Adding to Yuval's comment: conversely, a non-relativizing proof won't show that the statement doesn't relativize. A non-relativizing proof simply doesn't give any information about whether the result in question relativizes or doesn't. $\endgroup$
    – Noah Schweber
    Commented May 25, 2020 at 15:23
  • 1
    $\begingroup$ Yes, that is the conclusion. $\endgroup$
    – Yuval Filmus
    Commented May 25, 2020 at 15:28

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.