As the question states, does the integer-factorization problem fall into the class of NP-Complete problems?
views:
73answers:
1
+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
2010-04-15 03:20:17