Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is itself NP-complete as well? Would such a thing have any practical meaning?
1
-
3$\begingroup$ en.wikipedia.org/wiki/… $\endgroup$– adrianNCommented Oct 7, 2016 at 11:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are better than, say, reducing integer factorization to SAT and then using a SAT solver.
answered Oct 7, 2016 at 11:43