8
$\begingroup$

I am interested in how one proves that a sentence relativizes. Of course, proving that a sentence does not relativize is simple, as seen in the Baker-Gill-Solovay result; but how does one prove that a sentence does relativize, i.e., that it is true relative to any oracle? Are there known techniques for achieving this for arbitrary sentences?

If you know of any references that address this question, I would like to hear of them. Thanks.

$\endgroup$
  • $\begingroup$ isn't it enough to have a proof of the sentence that works relative to all oracles? a typical example will be hierarchy theorems. $\endgroup$ – Sasho Nikolov Sep 30 '13 at 20:48
  • $\begingroup$ I'm not sure. What if you are not sure if the sentence is true, but you'd like to know if the sentence would relativize if it were true? $\endgroup$ – Philip White Sep 30 '13 at 20:57
  • $\begingroup$ What is the definition of "sentence relativizes"? What do you mean by "techniques for achieving this for arbitrary sentences"? $\endgroup$ – Kaveh Sep 30 '13 at 22:08
  • 1
    $\begingroup$ well i guess proving it relative to any oracle is still one technique :) i am wondering if we know any example of a proposition about TMs which is not proven but is known to be either true or false relative to any oracle (that is what you mean right? as Kaveh said, some formalization would help) $\endgroup$ – Sasho Nikolov Sep 30 '13 at 22:37
  • 1
    $\begingroup$ @Kaveh, I mean a mathematical statement that (presumably) makes reference to Turing machines. The statement "relativizes" if, in the event that we add an oracle for a Turing machine, the statement remains true or false. $\endgroup$ – Philip White Oct 1 '13 at 0:20
12
$\begingroup$

Normally, the way people prove that a complexity theorem relativizes is using the following two-step procedure:

  1. Prove the theorem.

  2. Observe that your proof relativizes! In other words, that nothing in the proof changes at all if all the machines mentioned in the proof get access to the same oracle A.

Yes, it's really as simple as that. To make it rigorous, you should rewrite the whole proof adding superscripts of "A" all over the place. In practice, though, if people notice this issue at all, they'll usually just add a remark like "this result is easily seen to relativize."

If people seem cavalier about this, it's because they've learned, from experience, that only certain techniques (such as arithmetization) can possibly cause a proof not to relativize. So if your proof doesn't use those techniques, then it relativizes.

(A close analogy: suppose you prove a theorem about real numbers, but your proof never uses anything about the reals other than the fact that they're a field. Then it suffices to note that fact, to show that an analogous theorem must hold for complex numbers, p-adics, etc. There's no need to redo the proof.)

The one situation where more discussion is necessary, is where it's not even obvious what it means to relativize your theorem. (E.g., what's the oracle access mechanism?) As Kaveh pointed out above, there's no well-defined mathematical operation of "relativizing" a complexity theorem, just like there's no well-defined mathematical operation of "complexifying" a theorem about real numbers. Notice that, in the latter case, it's not enough to replace every occurrence of R by C: you probably also need to replace x2 by |x|2 (in some places, not others!), and make other changes that are "obvious" to a mathematician but hard to list formally. Likewise, in complexity theory, it's usually obvious what it means to "relativize" a theorem (i.e., who should get access to A, and what does it mean for them to access it?), but in some cases it can be quite subtle. See here for more about this issue.

Turning your question on its head, one could ask:

Is there any example of a relativizing complexity theorem, for which it's significantly harder to prove that the theorem relativizes than that the theorem is true?

Interestingly, I can't come up with a single indisputable example (though maybe someone else can)! Here's the best I can do:

  1. Recent work on blind and authenticated quantum computing (by Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani, and others) might lead to examples. In those cases, the situation is that we don't know whether the theorems relativize or not---but if they do relativize, then certainly a new idea will be needed beyond what's in the existing proofs.

  2. Arguably, another example might be the random self-reducibility of #P. If you asked most complexity theorists why that was true, they'd probably say it's because the permanent is both #P-complete and random self-reducible. That's true, but it doesn't answer the question of whether #P is rsr relative to any oracle. Well, it turns out that #P is rsr relative to any oracle, and it's not even hard to prove it---but you need to give a direct argument using polynomials, rather than appealing to properties of the permanent.

  3. In Section 8 of my and Avi Wigderson's algebrization paper, we showed that the GMW theorem (that NP has computational zero-knowledge proofs) is algebrizing. And that really did take new ideas: not "dramatically" new, but certainly nowhere to be found in the usual proofs of the GMW theorem. Of course, this is for algebrization rather than for relativization.

Addendum: In answer to a further question of the OP, I don't know of any techniques whatsoever for showing that, if you could prove a certain complexity conjecture (which you haven't yet), then your proof would necessarily relativize. Yes, as long as you restrict your "search for a proof" to relativizing techniques only, you can be sure that, if you ever succeed in finding a proof, then your proof will necessarily relativize. And in practice, that's often what people do (e.g., because they have certain ideas about what a proof would look like, and those ideas relativize). But I don't know of any way to guarantee, a priori, that by broadening your search to include non-relativizing techniques, you couldn't find a proof that had eluded you before.

$\endgroup$
  • $\begingroup$ I looked through section 8 of your paper, and am stumped by the bottom of page 40. $\:$ How does the prover give zero-knowledge proofs for parts (1) to (4)? $\:$ Even "the standard clauses are satisfied" involves the oracle to check the validity of decommitments. $\:$ While recursion may be intended, it is far from clear to me that recursion would be able to reach a small enough set of base cases. $\;\;\;$ $\endgroup$ – user6973 Feb 5 '14 at 2:50
  • $\begingroup$ (Now for a minor tangent matter.) $\:$ Do you know whether or not this paper's positive results in the hidden bits model (and a modified version), as I summarized in the 6-line paragraph in the middle of this answer, algebrize? $\:$ Unlike SAT, I don't see any way to relativize or algebrize directed Ham-cycle. $\;\;\;$ $\endgroup$ – user6973 Feb 5 '14 at 2:55
  • $\begingroup$ @RickyDemer comments aren't indexed by search features, and are not encouraged for lengthy discussions or new Q&As. It might be worthwhile to create a separate question (with a link to this answer) either here or on CS.SE based on your comments and then Scott or other users can address them in a matter that is more in-line with site mechanics. $\endgroup$ – Artem Kaznatcheev Feb 6 '14 at 5:38

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.