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

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

The problem with that argument is that we don't really know if those protocols are secure.

In fact we know that if P=NP most, if not all, would *not* be secure. So we are *less* confident of that than we are that P!=NP.

A proof that P!=NP (or that P=NP) would be a very surprising result! We would *expect* such a proof to lead to many other surprising results.

So knowing that a proof of a certain kind that P!=NP would also result in the proof of some particular surprising results doesn't really add much information.

Ralph Hartley
.