Tim Cook <z99### [at] gmailcom> wrote:
> On 2010-08-10 01:27, Warp wrote:
> >    If P != NP indeed is correct, then it's certain that no algorithm can
> > exist that cracks an NP encryption in polynomial time. Not now, nor any
> > time in the future.

> You mean 'certain that no algorithm can brute-force *all combinations* 
> of an NP encryption in polynomial time.'  Merely cracking is somewhat 
> more trivial, since you (usually) don't need to go through every 
> possibility.

  If P != NP, then there can't exist an algorithm which takes any given
input and solves a provably NP problem on that input in polynomial time.

  Of course that doesn't mean that *no* inputs can be solved in polynomial
time (it's rather easy to give trivial individual examples of any NP problem
which can be solved very fast). It means that you can't write a program
which cracks all files encrypted with a certain algorithm in polynomial
time. (And in fact, due to the nature of most NP problems, it won't be
able to crack almost *any* such problem in polynomial time, except for
extremely trivial situations.)

  (Of course we have to remember what the 'N' stands for in "NP". It
doesn't stand for "non", as many people erroneously think. It stands for
"non-deterministic". This means that a non-deterministic algorithm can
solve the problem in polynomial time. Of course implementing this would
need some new physics to be discovered. Quantum computing is the most
promising one, but might not lead anywhere.)

-- 
                                                          - Warp

Post a reply to this message