Re: Significance of "Relativizations of the P =? NP Question"

tchow@xxxxxxxxxxxxx wrote:
> In article <1137942430.592765.122510@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> <examachine@xxxxxxxxx> wrote:
> >Could you please tell me a bit about this paper? What does it imply
> >for a potential solution?
>
> I assume you mean the paper by Baker, Gill, and Solovay. This shows that
> there's an oracle X with respect to which P^X = NP^X, and there's another
> oracle Y with respect to which P^Y != NP^Y.
>
> Most proofs in complexity theory---let's take P != EXPTIME as an
> example---can easily be relativized. That is, you can easily modify
> the proof to show that P^X = EXPTIME^X for *any* oracle X.
>
> The Baker-Gill-Solovay result shows that any proof of P != NP cannot
> relativize. Therefore, when you're trying to construct a proof of P != NP,
> you should ask yourself, "What happens when I try to relativize this proof?
> Where does it break down?" If there isn't any step in your proof that
> resists relativization, then your proof can't possibly work.
>
> The most famous examples of proofs in complexity theory that don't
> relativize come from the area of interactive proofs. For example, Shamir
> proved that IP = PSPACE, even though there is an oracle that separates the
> two. There is some debate as to "which step" of the proof is the one that
> can't be relativized. It is an interesting open problem to define precisely
> what a "relativization of a *proof*" (as opposed to a single statement like
> P = NP) means. It's clear in specific examples what it means, but a
> satisfactory general theory is lacking.

I'm grateful for your explanations. There are not many people who
are interested in these important fundamental problems in computer
science in my department. It seems that everybody is busy publishing a
paper.

It is interesting that you say a general theory is lacking. I've read
your post with great interest. Thank you again for taking the time to
answer me. It seems essential to understand this for anybody who is
trying to prove P!=NP or the other way around. I am suspecting that
many proposed proofs would fail this litmus test.

I was once thinking about whether a diagonalization proof was possible,
but then I had realized that I was going in circles. I think you said
in one post that not all diagonalization proofs necessarily relativize,
or something like that, if you can make sense of my (probably
inaccurate) sentences, could you please explain that? Can there be a
proof for NP?=NP question by diagonalization or is some other proof
method necessary? What would be the most important property of a proof
that does not relativize? That is, although you say a general theory is
lacking, you should have some ideas about what it means intuitively for
the proof, right?

Best Regards,

--
Eray

.

Relevant Pages