Re: Protein folding and P = NP

newstome_at_comcast.net
Date: 01/24/04 

Date: Sat, 24 Jan 2004 16:54:38 GMT

Arthur J. O'Dwyer <ajo@nospam.andrew.cmu.edu> wrote:
> On Fri, 23 Jan 2004 newstome@comcast.net wrote:

>> *ALL* public-key encryption algorithms depend on P != NP to some
>> extent. If P=NP, with efficient solutions for NP-complete problems,
>> then everything we use now would be insecure.
>
> You could have left out the "If P=NP" part of that sentence, and
> it would still have been true. Real-world efficiency has very little
> to do with a problem's being NP-complete or not.

I disagree with that, as things exist in the real world. The
mathematical definitions of P and NP don't require that all
NP-complete problems are inefficient or that all polynomial time
algorithms are efficient (in fact, the latter is obviously false).
However, in the real world, with real problems, the following *is*
true: almost all (the overwhelming majority) of problems that we know
to be in P have efficient, practical algorithms, and no known
NP-complete problem has a known efficient algorithm except for special
subcases or approximations (pseudo-polynomial time algorithms for
knapsack or subset sum, for instance, or approximation algorithms for
some other problems such as TSP).

To dismiss the P vs. NP problem as having little to do with real-world
efficiency is either a knee-jerk anti-theory reaction that some people
seem to have, or simply being naive.

>> The security isn't *equivalent* to the P vs. NP problem though. If
>> P=NP (efficiently) then everything's toast. If P!=NP, then some
>> algorithms could still be toast.
>
> Right, wrong, and vacuous, respectively. To elaborate: Security is
> orthogonal to NP-ness; security is orthogonal to NP-ness; and some
> algorithms are designed by idiots, respectively.

No, security is not orthogonal to NP-completeness. Again, if P=NP
through efficient algorithms and reductions, then all current widely
used PK encryption is toast. That's hardly "orthogonal".

>> A better explanation: if P=NP, then factoring and discrete log (over
>> Zp or elliptic curves or whatever other efficiently computable cyclic
>> group you want to consider) have polynomial time algorithms. If these
>> are efficient (low exponent/constant) algorithms, then the whole
>> crypto world would be in for a big shock....
>
> But it's "obvious" that there are no such low-exponent algorithms
> for factoring, et al., so even if someone invents an O(n^10) algorithm
> for factoring 'n' tomorrow, things will probably remain safe. Note
> the quotation marks: it's not really obvious, in that nobody knows
> whether it's even true or not, but it seems eminently reasonable to
> assume it for the time being.

I'd say that your first statement is no more "obvious" than the entire
P vs. NP question. The fact is that we just don't know.

Yes, even if P=NP, there's a chance that we could find one-way
trapdoor functions such that evaluating the function is soemthing like
O(n) but the inverse is something like Omega(n^10), so we'd still have
viable public key crypto. But since I strongly believe (after almost
20 years of research in algorithms and complexity theory) that it's
highly unlikely that P=NP, or that strongly NP-complete problems are
solvable with practical (albeit super-polynomial) algorithms, that's
pure speculation that we really don't even need to get into.... 

-- 
That's News To Me!
newstome@comcast.net

Relevant Pages

  • Re: Protein folding and P = NP
    ... > So would most kinds of public-key encryption. ... > know any PKE schemes that rely explicitly on P!= NP, ... If P=NP, with efficient solutions for NP-complete problems, ... group you want to consider) have polynomial time algorithms. ...
    (comp.theory)
  • randomized algorithms for np-complete problems
    ... Does anyone know of any good links to articles about randomized ... algorithms for solving np-complete problems? ...
    (comp.theory)
  • Re: Search space algorithms for NP-complete problems?
    ... space algorithms for NP-complete problems. ... In my undergraduate algorithms class, ...
    (comp.theory)
  • Re: Size of RN vs USN (Was: Germany Still Loses BB...) [OFFTOPIC, BUT INTERESTING]
    ... >algorithms exist which would solve these problems in polynomial time ... A problem in P is one that can be solved in polynomial time (i.e., ... Any cipher *has* to be in NP, since you have to have a nice ... reasonable-length key can be broken depends on the P=NP ...
    (soc.history.war.world-war-ii)
  • Re: Could P = NP be true?
    ... Tim Little wrote: ... All known algorithms have cases where the runtime is not ... SAT in polynomial time would prove that P!= NP. ... Dialogues Concerning Two New Sciences ...
    (comp.theory)