-3
$\begingroup$

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring.

So supposing status of Cramer's conjecture remains uncertain (that is it is not known to be true/false or undecidable), then is there any consequence of polynomial time algorithm to this variant factoring problem assuming that Cramer's conjecture cannot be removed from the reduction? That is could such an algorithm be of any value other than breaking RSA and some number theory problems? Could we use this algorithm to solve other problems in $\mathsf{NP}$. Would this still imply at least $\mathsf{NP}\subseteq\mathsf{RP}$? Where in Impagliazzo's five worlds would we be in?

Update: What is minimum number of distinct primes one needs in $N$ for completeness of this problem under Cramer's conjecture? How many such numbers are there?

$\endgroup$
  • $\begingroup$ Why would Cramer's conjecture need to be true? $\;$ $\endgroup$ – user6973 Aug 15 '15 at 7:35
  • $\begingroup$ I have a modified cramer's conjecture (note that I have used $k$-almost prime instead of prime). Read comments in attached stackexchange link. $\endgroup$ – Brout Aug 15 '15 at 7:39
  • $\begingroup$ Can you be more specific? $\;\;\;$ There are 49 comments at that link, and I have no clue how any of them would yield implications from $\:$ P = NP $\;$. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user6973 Aug 15 '15 at 7:45
  • $\begingroup$ If $P=NP$, then there is a deterministic reduction from subset sum to this problem. Shouldn't this say gaps of primes are small? I could be wrong. This is the reasoning. $\endgroup$ – Brout Aug 15 '15 at 8:03
  • $\begingroup$ No. $\:$ Such a reduction could just consist of solving the subset sum instance and then outputting some otherwise-arbitrary instance of this problem with the same answer. $\;\;\;\;$ $\endgroup$ – user6973 Aug 15 '15 at 8:11
3
$\begingroup$

ZPP = NP ​ is a "consequence of polynomial time algorithm to this variant factoring problem", which can be deduced by replacing Cramer's conjecture with zero-error randomness,
rather than just removing Cramer's conjecture. ​ ​ ​ ​ Accordingly, we would be in Algorithmica.

One can simply test randomly chosen numbers in the relevant intervals
for primality, rather than choosing them deterministically.

Unless ​ NP $\hspace{-0.02 in}\subseteq$ BQSUBEXP ​ infinitely often, one needs [input_length]$^{\hspace{.03 in}\Omega \hspace{.02 in}(1)}$ distinct primes
"in $N$ for completeness of this problem under Cramer's conjecture",
since Shor's algorithm can be used to find the prime factors, and given those,
this problem can be solved by trying the products of each submultiset of those primes.
There are lots of such numbers, since there are lots of primes.


Products of n distinct $\big[$primes less than $2^{\hspace{.02 in}n}\hspace{-0.03 in}\big]$ are less than $2^{\hspace{.02 in}n^2}\hspace{-0.06 in}$, so their number of distinct prime factors is not less than [their_length]$^{1/2}$. ​ ​ ​ ​ According to wikipedia, since 2 is the only power of 2 that's prime, if ​ 6 ≤ n ​ then $\big[$the number of primes less than $2^{\hspace{.02 in}n}\hspace{-0.03 in}\big]$ is greater than $\dfrac{2^{\hspace{.02 in}n}}{\ln \hspace{-0.03 in}\left(2^{\hspace{.02 in}n}\right)\hspace{-0.03 in}+\hspace{-0.03 in}2}$.

For all n, if ​ 20 ≤ n ​ then $\ln \hspace{-0.03 in}\left(2^{\hspace{.02 in}n}\right)\hspace{-0.03 in}+\hspace{-0.03 in}2 \: = \: (n\hspace{-0.03 in}\cdot \hspace{-0.03 in}\ln(2))+2 \: = \: (\ln(2)\hspace{-0.03 in}\cdot \hspace{-0.03 in}n)+2 \: < \: \Big(\hspace{-0.05 in}\frac7{10}\hspace{-0.03 in}\cdot \hspace{-0.03 in}n\hspace{-0.04 in}\Big)+2 \: \leq \: \Big(\hspace{-0.05 in}\frac7{10}\hspace{-0.03 in}\cdot \hspace{-0.03 in}n\hspace{-0.04 in}\Big)+\Big(\hspace{-0.05 in}\frac1{10}\hspace{-0.03 in}\cdot \hspace{-0.03 in}n\hspace{-0.04 in}\Big) \: = \: \frac45 \cdot n \;\;\;$.

For all n, if ​ 20 ≤ n ​ then $\: \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}n = \dfrac{\frac54 \hspace{-0.05 in}\cdot \hspace{-0.03 in} 2^{\hspace{.02 in}n}}n = \dfrac{2^{\hspace{.02 in}n}}{\frac45 \hspace{-0.05 in}\cdot \hspace{-0.03 in}n} < \dfrac{2^{\hspace{.02 in}n}}{\ln \hspace{-0.03 in}\left(2^{\hspace{.02 in}n}\right)\hspace{-0.03 in}+\hspace{-0.03 in}2}$.

For all n, if ​ 20 ≤ n ​ then there are more than $\dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}n$ primes less than $2^{\hspace{.02 in}n}$.

For each such n, one can choose n disjoint sets of at least $\left\lfloor \hspace{-0.05 in} \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}}\hspace{-0.04 in} \right\rfloor$ of those primes.


For all n, if ​ 20 ≤ n ​ then $\;\;\; \dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}} \: = \: \dfrac{4\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}} \: < \: \dfrac{\left(4\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)\right)+2^{\hspace{.02 in}n-2}\hspace{-0.04 in}-n^2}{n^{\hspace{.02 in}2}}$

$= \: \dfrac{4\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}} \: < \: \dfrac{\left(5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)\right)\hspace{-0.02 in}-n^2}{n^{\hspace{.02 in}2}} \: = \: \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}}-1 \: < \: \left\lfloor \hspace{-0.05 in} \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}}\hspace{-0.04 in} \right\rfloor \;\;\;$.


For all n, if ​ 20 ≤ n ​ then one can choose n disjoint sets of at least $\dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}}$ primes less than $2^{\hspace{.02 in}n}$.

For all n, if ​ 20 ≤ n ​ then at least $\bigg(\hspace{-0.04 in}\dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}}\hspace{-0.06 in}\bigg)^{\hspace{-0.04 in}n}$ number less than $2^{\hspace{.02 in}n^2}$ have n distinct prime factors.

For all n, $\; \bigg(\hspace{-0.04 in}\dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}}\hspace{-0.06 in}\bigg)^{\hspace{-0.04 in}n} = \dfrac{\left(2^{\hspace{.02 in}n}\hspace{-0.02 in}\right)^n}{\left(\hspace{-0.02 in}n^{\hspace{.02 in}2}\hspace{-0.04 in}\right)^{\hspace{-0.02 in}n}} = \dfrac{2^{\hspace{.02 in}n\cdot n}}{n^{\hspace{.02 in}2\cdot n}} = \dfrac{2^{\hspace{.02 in}n^2}}{n^{\hspace{.02 in}2\cdot n}} \:\:$.

Therefore, for all n, if ​ 20 ≤ n ​ then at least $\dfrac{2^{\hspace{.02 in}n^2}}{n^{\hspace{.02 in}2\cdot n}}$ numbers less than $2^{\hspace{.02 in}n^2}$ are
such that their number of distinct prime factors is not less than [their_length]$^{1/2}$.

$\endgroup$
  • $\begingroup$ do you mean this mathoverflow.net/questions/212816/…? Could you add your knowledge on replacing Cramer's conjecture in a more down to earth way? $\endgroup$ – Brout Aug 20 '15 at 4:02
  • $\begingroup$ What is the definition of an 'effective result'? $\endgroup$ – Brout Aug 20 '15 at 4:05
  • $\begingroup$ I believe 'effective result' is defined in the same way as "constructive result", although the term 'effective' would be used far less often in continuous math. ​ ​ $\endgroup$ – user6973 Aug 20 '15 at 4:53
  • $\begingroup$ Could you give an estimate on 'lots of such numbers'? Your 'effective' result is still vague otherwise I am happy with your post. $\endgroup$ – Brout Aug 20 '15 at 4:55
  • 1
    $\begingroup$ The analogue to $\: NP \subseteq P/poly \:$ for Impagliazzo's worlds would be that we're not in Minicrypt or Cryptomania with respect to non-uniform adversaries. $\;\;\;\;$ $\endgroup$ – user6973 Aug 21 '15 at 12:28

Your Answer

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

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