In the post on site cstheory.stackexchange on whether a variant of integer factorization $$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ integer}\mbox{ } m \in \{a, \ldots, b\}\mbox{ }\mathsf{ such}\mbox{ }\mathsf{that}\mbox{ }m | n\}$$ is $\mathsf{NP}$ complete, it is clear that difference $b-a$ can neither be too small nor too big for the problem to remain $\mathsf{NP}$ complete under Cramér's conjecture.

What is the possible range of difference $b-a$ under which the problem remains $\mathsf{NP}$ complete under Cramér's conjecture?

Note in this problem $m$ need not be prime which makes the problem combinatorial rather than arithmetical

  • 1
    $\begingroup$ I don't understand - it is not even known that factorization is NP-complete. $\endgroup$ – Igor Rivin Nov 1 '15 at 22:13
  • $\begingroup$ This is a variant of factorization $m$ need not be prime. $\endgroup$ – Brout Nov 1 '15 at 22:40
  • $\begingroup$ @IgorRivin Check out answer and comments in link included in post $\endgroup$ – Brout Nov 2 '15 at 0:24
  • $\begingroup$ Factorization is factorization. It's still arithmetical, not combinatorial. $\endgroup$ – Gerry Myerson Nov 2 '15 at 0:28
  • $\begingroup$ no this is not arithmetical at all, you can factorize into primes which are small but $m$ needs to be pieced together (this last step is not at all arithmetical) into a factor which is exponential in compared to any of prime factors $\endgroup$ – Brout Nov 2 '15 at 0:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.