3
$\begingroup$

The exact complexity of factoring integers (the decision problem) is a major open question in TCS (with important implications, especially in cryptography because of the RSA algorithm), and is widely conjectured to lie "between" P and NP-complete (see the AKS algorithm and Shor's algorithm for two other key aspects of its significance).

Yet, there is so much diversity among the NP-complete problems, including some relating to factoring types of objects and problems in number theory.

What are some of the "closest" or "nearest" NP-complete problems to integer factoring?

Optionally, an answer might indicate why such problems are thought not to be equivalent to integer factoring under polynomial time reductions (even circumstantial evidence would be appreciated).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

The textbook of Computational Complexity: Modern Approach, by Arora and Barak gives such example:

They define the decision problem Integer Factoring on input of three positive integers,

$\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$.

They state that Alon and Kilian showed that if integer $p$ is not required to be prime number then the problem becomes $NP$-complete.

Improve this answer
$\endgroup$
6
  • 5
    $\begingroup$ cstheory.stackexchange.com/questions/4769/… $\endgroup$
    – Huck Bennett
    Jun 21, 2013 at 18:01
  • $\begingroup$ p.39 in other words "Given three numbers N, L, U decide if N has a prime factor p in the interval [L, U]. The certificate is the factor p." on p.58 it is stated the NP complete case is an unpublished result from personal communication. does anyone know if its ever been published? $\endgroup$
    – vzn
    Jun 21, 2013 at 18:58
  • 1
    $\begingroup$ @vzn I don't believe that the proof has been published before. Personaly, I searched a lot for it with no luck. $\endgroup$
    – Mohammad Al-Turkistany
    Jun 21, 2013 at 19:21
  • $\begingroup$ What is the current status of this? On p2.4 (42) of theory.cs.princeton.edu/complexity/book.pdf it says "The Graph Isomorphism and Factoring problems are not known to be either in P nor NP-complete." where they have defined the Factoring problem in example 2.2 as in this answer. $\endgroup$
    – user15587
    Jun 5, 2019 at 11:01
  • $\begingroup$ @Anush I believe there are no updates $\endgroup$
    – Mohammad Al-Turkistany
    Jun 5, 2019 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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