views:

73

answers:

1

As the question states, does the integer-factorization problem fall into the class of NP-Complete problems?

+6  A: 

Factoring:

  • It is not known to be NP-complete. (No reduction from an NP-complete problem has been found.)
  • It is not known not to be NP-complete either (if we knew the latter about some nontrivial problem in NP, it would mean P≠NP, so the latter is not surprising).
  • No polynomial factoring algorithm is known (or believed to exist), so it is believed not to be in P either.

The informal consensus/belief is that this is one of the "in-between" problems that are not in P and are not NP-complete. Of course, this belief is less strong and widely held than P≠NP.

ShreevatsaR