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?
Are all proof techniques which only look at black box behaviour of a TM relativizing?
complexity theory;turing machines;proof techniques;oracle machines;relativization
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)$.