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

In article <1137973965.941627.117770@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<examachine@xxxxxxxxx> wrote:
>Can there be a proof for NP?=NP question by diagonalization or is some
>other proof method necessary?

That depends on how you define "diagonalization." I recommend that you read
"Universal languages and the power of diagonalization" by Nash, Impagliazzo,
and Remmel (COMPLEXITY 2003) for more information. I think the paper should
be available on the web.

>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?

Very roughly speaking, you need to "dig into the details" of NP problems,
and cannot rely solely on a proof technique that deals only with "general
properties" of NTM's. "General properties" tend to relativize, i.e., they
make just as much sense for an oracle NTM as for a "true" NTM.

By the way, the other important obstacle to P != NP proofs is
naturalization. Look up Razborov and Rudich's paper "Natural Proofs"
this one is definitely on the web). Again, very roughly speaking, this
shows that a proof that is "too explicit" is unlikely to be able to
separate P from NP, because you could turn such a proof into something
that breaks cryptographic protocols that are believed to be secure.

So, somewhere in between "too general" and "too explicit" lies the
elusive golden mean...
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.