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$ – T.... Nov 1 '15 at 22:40
  • $\begingroup$ @IgorRivin Check out answer and comments in link included in post $\endgroup$ – T.... 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$ – T.... Nov 2 '15 at 0:54

Your Answer

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

Browse other questions tagged or ask your own question.