Skip to main content
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link

In the post on site cstheory.stackexchangepost 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

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

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

deleted 67 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

In the questionpost 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. Note in this problem Cramér's conjecture states that the difference between two consecutive$m$ need not be prime numbers $p_n$ and $p_{n+1}$ is asymptotically $O(\log^2 p_n)$.which makes the problem combinatorial rather than arithmetical

In the question 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. Cramér's conjecture states that the difference between two consecutive prime numbers $p_n$ and $p_{n+1}$ is asymptotically $O(\log^2 p_n)$.

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

Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

On variant of integer factorization

In the question 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. Cramér's conjecture states that the difference between two consecutive prime numbers $p_n$ and $p_{n+1}$ is asymptotically $O(\log^2 p_n)$.