4
$\begingroup$

Possible Duplicate:
What are the consequences of factoring being NP-complete?

What notable reference works have covered this?

$\endgroup$

marked as duplicate by Tsuyoshi Ito, Robin Kothari, Kaveh Feb 8 '11 at 9:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 7
    $\begingroup$ en.wikipedia.org/wiki/Integer_factorization $\endgroup$ – Aaron Sterling Aug 17 '10 at 15:50
  • 5
    $\begingroup$ I think this may be a more suitable question if rephrased as: "What are the consequences of factoring being NP-complete?" But as stated, it's all answered on the wikipedia page (btw, first hit on google for "integer factorization"). $\endgroup$ – Moritz Aug 17 '10 at 16:12
  • 4
    $\begingroup$ I believe Moritz's comment here is insightful, txwikinger. Questions that, as asked, can be answered by a quick Wikipedia or Google search are outside the scope of this site (Disclaimer: This is my opinion, and appears to be the opinion of some others as well.). Variations on the theme that explicitly dig deeper into what is less readily available on the Internet already can be very useful however. $\endgroup$ – Daniel Apon Aug 17 '10 at 16:18
  • 1
    $\begingroup$ @Daniel Apon: Well, I take the advise, however, it does not make sense to make a proposal in which this exact question is voted as on-topic without any counter votes, and then say it is off-topic. Somewhere there has to be some sanity, that people know what this site is about! $\endgroup$ – txwikinger Aug 17 '10 at 16:31
  • 3
    $\begingroup$ Yes, I agree that it is a problem. Hopefully kinks like this will be ironed out as time passes. In general, though, I think the fear is that the site could degenerate to a place for students to ask homework questions if "less interesting" questions are allowed (for an appropriate interpretation of "less interesting"). One of the important goals is to promote advanced Q&A, since there has been a noticeable lack of this elsewhere for CS theory. $\endgroup$ – Daniel Apon Aug 17 '10 at 16:47
24
$\begingroup$

No, its not known to be NP-complete, and it would be very surprising if it were. This is because its decision version is known to be in $\text{NP} \cap \text{co-NP}$. (Decision version: Does $n$ have a prime factor $\lt k$?)

It is in NP, because a factor $p \lt k$ such that $p \mid n$ serves as a witness of a yes instance.

It is in co-NP because a prime factorization of $n$ with no factors $\lt k$ serves as a witness of a no instance. Prime factorizations are unique, and can be verified in polynomial time because testing for primality is in P.

$\endgroup$
  • $\begingroup$ yes; apparently, Shor's algorithm can be used to solve it in polynomial time on a quantum computer, whereas iirc. most NP complete algorithms did not have P-time quantum versions. $\endgroup$ – gatoatigrado Aug 17 '10 at 15:54
  • $\begingroup$ wouldn't that be all not most NP complete algorithms do not have P-time quantum algorithms, give the NP complete reduction? $\endgroup$ – Simon Jul 15 '14 at 20:58
  • 1
    $\begingroup$ Can you explain why it will be "surprising" if $\text{NP}\subseteq \text{NP}\cap \text{co-NP}$? $\endgroup$ – Jus12 Sep 26 '16 at 17:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.