Re: Protein folding and P = NP

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 01/23/04 

Date: Fri, 23 Jan 2004 12:43:32 -0500 (EST)

On Thu, 22 Jan 2004, Russell Easterly wrote:
>
> "mike3" <mike4ty4@yahoo.com> wrote in message
> news:1d54b7e4.0401212326.607dc994@posting.google.com...
>
> > Well, if P = NP, then crypto is toast.
> > > -Arthur

  I didn't write that. Please watch your attributions.

> Certain types of public key encryption would be toast.
> A "one time pad" system would care less.

  So would most kinds of public-key encryption. In fact, I don't
know any PKE schemes that rely explicitly on P != NP, although
lots of them rely on the fact that O(2^n) >> O(n) for large values
of n. P=NP wouldn't change this fundamental fact in the slightest.

-Arthur

Relevant Pages