I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier.

However, it is hard to find a concrete definition of a "relativizing" proof. The best defintion I have found is as follows: "A relativizing proof is any proof that is insensitive to the presence of oracles". So any proof technique that cannot tell if a TM used an oracle is relativizing.

Now my question is: Does this imply that all relativizing proofs only look at the black box behaviour of TMs? Moreover, are all proofs which only look at the black box behaviour of TMs also relativizing? Or are there cases where a proof is relativizing but is not looking at the black box behaviour of a TM, or vice-versa?

  • $\begingroup$ Indeed, proofs which treat the Turing machines as a black box tend to relativize, and vice versa. I think that the more interesting question is, what are some non-relativizing proof techniques. Hopefully you'll see several of these as the seminar progresses. $\endgroup$ – Yuval Filmus Jun 15 '17 at 8:15
  • $\begingroup$ @YuvalFilmus Since you say "tend to relativize", does that mean that there is a black box proof that does not relativize? Or does this hold for all such proofs? $\endgroup$ – Rednaxel59 Jun 15 '17 at 11:47
  • $\begingroup$ To answer this, you will need to formally define "black box proofs" and "relativation", and only then the question can be asked. $\endgroup$ – Yuval Filmus Jun 15 '17 at 16:15

A theorem about an oracle Turing machine $T^A$ (where $A$ is the oracle) is relativizing if it is of the form $$\forall A \,.\, \phi(T^A)$$ We say that the statement $\phi$ relativizes. There is no requirement on how such a statement is proved, i.e., we do not assume that we only observe the "black box" behavior of $T$ or anything like that. In fact, it is clear that this cannot be the case, as one can easily prove a relativizing theorem about Turing machines which speaks about how the machine works.

Often we start with a theorem about an ordinary Turing machine, and later we ask whether the theorem relativizes. This just means that we first proved $\phi(T^\emptyset)$, and now we wonder whether the trivial oracle $\emptyset$ could be replaced with an arbitrary one $A$ so that we get $\forall A \,.\, \phi(T^A)$.

  • $\begingroup$ So it's logical statements themselves that relativize. Thank you for clearing this up for me! $\endgroup$ – Rednaxel59 Jun 16 '17 at 13:48

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.