Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top