According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other implications yet- like if P != NP, does this mean that Integer Factorization is necessarily not in P? Conversely, if Integer Factorization is in P, does this imply anything about the polynomial hierarchy? Thanks.

  • $\begingroup$ Not 100% sure, but I think the gist is that we don't know much. The fact that primality testing is in $P$ with such a high exponent has led some people to belive that factorization might be in $P$, but I don't actually have a reference for this, I just remember hearing it somewhere, so I could be wrong. $\endgroup$ – jmite Jul 17 '14 at 16:57
  • $\begingroup$ @jmite, I don't think anyone conjectures that factoring is in $P$. You are right that we don't know much. $\endgroup$ – D.W. Jul 18 '14 at 5:50

Before answering your questions a distinction has to be made, when talking about $NP$ completeness we are talking about the decision problem not the function problem, which is given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M.

So answering your questions in order, Since integer factorization is not known to be NP complete, $P \neq NP$ would not cause it to automatically not be in $P$ since quite often things that were thought to be in $NP$ are moved to $P$, only an $NP$ complete problem would be excluded from being in $P$. For the second one, again since it is not $NP$ complete a polynomial time solution to it will not effect the hierarchy for the same reason as before.

As an extra note, the actual location of factorization in the hierarchy is unknown, we know is is $BQP$, $NP$, $co-NP$, $FNP$ and $UP$. It may end up being $NP$-Intermediate, but no one knows for sure.

| cite | improve this answer | |
  • $\begingroup$ Thanks. Although I'm a little confused by your answer- did you mean to write "not known to be NP-complete" rather than just "since integer factorization is not NP-complete". Wouldn't your statement imply P != NP since otherwise all languages in the polynomial hierarchy are NP-complete (i.e. in P)? $\endgroup$ – Ari Jul 18 '14 at 1:26
  • $\begingroup$ If you really want to get technical then yes, it is not known to be NP complete, also it is not believed to be. Current thoughts say that if $P\neq NP$ then it is not in P, NP complete, or co NP Complete. I'm not sure I follow on how you reached your conclusion though. Even if $P=NP$ not all problems would be in what was previously the NP complete category. $\endgroup$ – lPlant Jul 18 '14 at 2:18
  • $\begingroup$ We don't actually know that factoring is not NP-complete. If P=NP, then it trivially is. $\endgroup$ – Yuval Filmus Jul 18 '14 at 2:22
  • $\begingroup$ This is just a question of semantics in speech. Until you can show something to be NP complete to state that it is not is logical. Otherwise we would have to preface literally ever run time statement with it, such as, we do not know if checking if a number is even is NP complete. $\endgroup$ – lPlant Jul 18 '14 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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