|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |