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

tchow@xxxxxxxxxxxxx wrote:
Ralph Hartley <hartley@xxxxxxxxxxxxxxxx> wrote:
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.

This isn't quite fair. 

Perhaps not.

protocols *are* secure.  Simultaneously proving that P != NP and that
the protocols are *not* secure is somewhat more surprising than proving
P != NP only.


I guess I could agree with "somewhat".

Similarly, Razborov-Rudich suggests that it may be more promising to
look for a relatively easy non-natural proof of P != NP than to bang
one's head against the (most likely difficult) problem of breaking all
those cryptographic protocols.


Ah! The *easy* proof of P != NP! I'm all for that!

Ralph Hartley
.

Relevant Pages

  • Re: ? on the front of Japanese novels
    ... If I didn't know what "zen shōhin san wari biki" meant, I would have a hard time working out why Kawachi only charged me 70 yen for a green tea ice cream which said "100 yen" on the packet, or why I could buy my Makita router for only 42,000 yen from Joyful Honda. ... it's hardly surprising that individuals have gaps in ... The difference in this case is that not knowing that Edogawa Ranpo is a pun on Edgar Allen Poe is like not having furry dice in your car. ...
    (sci.lang.japan)
  • Re: muhammad was a paedophile.
    ... isn't very surprising. ... it's best not to pontificate upon subjects in which you know ... Which is a truly beautiful Judeo/Christian thought. ... knowing its meaning, they say this word to god every day and have no problem ...
    (alt.religion.islam)
  • Re: Am I the only one who likes spoilers?
    ... the experience of being befuddled by a story and not knowing what ... The more surprising the end, ... mystifies me. ... Lots of people test to find out the gender of their children. ...
    (rec.arts.sf.written)
  • Re: Am I the only one who likes spoilers?
    ... djheydt@xxxxxxxxxxx (Dorothy J Heydt) wrote, ... the experience of being befuddled by a story and not knowing what ... The more surprising the end, ...
    (rec.arts.sf.written)