Invisible <voi### [at] devnull> wrote:
> factorising numbers is an NP problem

  It's actually not that simple.

  NP problems are decision problems, where the answer is "yes" or "no".
Obviously "what are the factors of this number?" is not such a problem.
The integer factorization problem is an so-called function problem. It
trivially falls into FNP (the function-problem equivalent of NP), but it's
not known if it's also in FP (the function-problem equivalent of P).

  You can make integer factorization into a decision problem by posing it
as "does n have a factor which is smaller tham m?" (posing it like this
is theoretically rational and useful because if you found an algorithm
to solve that problem quickly, you could use it to factorize the number
quickly by using binary search). Again, it's not known which complexity
class this decision version of the problem falls into either.

-- 
                                                          - Warp

Post a reply to this message