Warp wrote:

>   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.)

Is it not also true that although, for example, factorising numbers is 
an NP problem, factorising the product of two Mersenne primes might turn 
out to have a polynomial-time algorithm?

Post a reply to this message