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

tchow@xxxxxxxxxxxxx wrote:
> 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.

Thank you very much for the information.

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

I see. I had intuitively understood this when I tried to define
the problem in a very high level way, say it makes this many
operations under this condition, etc. Such an approach didn't
seem to say much about the question at all I had noticed :{

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

Hm, yes, I have seen this in Wikipedia. Very interesting work.

> So, somewhere in between "too general" and "too explicit" lies the
> elusive golden mean...

Speaking out of ignorance, I have seen many proof attempts
working on the details of a specific NP-Complete problem such as
SAT. Would that be a good strategy?

Regards,

--
Eray

.