HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Complexity class of integer factorization

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
classintegercomplexityfactorization

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#64331, answer score: 9

Revisions (0)

No revisions yet.