1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I don't understand - it is not even known that factorization is NP-complete. $\endgroup$
    – Igor Rivin
    Commented Nov 1, 2015 at 22:13
  • $\begingroup$ This is a variant of factorization $m$ need not be prime. $\endgroup$
    – Turbo
    Commented Nov 1, 2015 at 22:40
  • $\begingroup$ @IgorRivin Check out answer and comments in link included in post $\endgroup$
    – Turbo
    Commented Nov 2, 2015 at 0:24
  • $\begingroup$ Factorization is factorization. It's still arithmetical, not combinatorial. $\endgroup$
    – Gerry Myerson
    Commented Nov 2, 2015 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$
    – Turbo
    Commented Nov 2, 2015 at 0:54

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .