Why is Relativization a barrier?

Problem Detail: 

When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to a friend, a question came up as to why such techniques are ill-suited for proving the $\mathsf{P} \neq \mathsf{NP}$ problem, and I couldn't give a satisfactory answer.

To put it more concretely, if I have an approach to prove $\mathsf{P} \neq \mathsf{NP}$ and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Any exposition/thoughts on this topic?

Asked By : Nikhil

Answered By : Tsuyoshi Ito

To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Note that the latter "if" is not a condition, because Baker, Gill, and Solovay already constructed such an oracle. It is just a mathematical truth that (1) there exists an oracle relative to which P=NP, and that (2) there exists an oracle relative to which P≠NP.

This means that if you have an approach to prove P≠NP and the same proof would equally prove a stronger result "P^A≠NP^A for all oracles A," then your approach is doomed to fail because it would contradict (1).

In other words, there is some fundamental difference between proving P≠NP and proving e.g. the time hierarchy theorem, because the proof of the latter just uses diagonalization and is equally applicable to any relativized world.

Of course, this does not mean that there is no proof for P≠NP. Such a proof (if one exists) must fail to prove the stronger result mentioned above. In other words, some part of the proof must distinguish the nonrelativizing world from arbitrary relativized worlds.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1271