After reading this post An NP-complete variant of factoring. I come up with a question.

To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides an given number n and $p$ is between a given interval $l \leq $p$ \leq u$. The variant of the factoring problem (VF) ask for a number $p$ that divides an given number n and $p$ is in the interval $l \leq $p$ \leq u$, but not necessarily needs to be prime. So while (F) is not believed to be NP-complete, (VF) is.

But couldn't you solve (VF) with polynominal many oracle calls to (F), by first getting all prime divisors of n. (This list, lets call it l, has at most $log_2(n)$ many entries) Then calculate all subset products of $l$. An upper bound for how many this could be, would be given by the number of ways of choosing $i$ many elements from $l$, for $i = 0$ to $log_2(n)$. So $\sum_{i = 0}^{log_2(n)} \binom{log_2(n)}{i} = 2^{log_2(n)} = n$. So there also polynominal many products, which needs to be checked if they are between $l$ and $u$.

Wouldn't this make Factoring also NP-complete?

  • 1
    $\begingroup$ i think the error is that there a exponentiell number of products, since it is $n$. $\endgroup$ – user3680510 Jan 12 '16 at 8:06
  • 1
    $\begingroup$ It seems you answered your own question. $\endgroup$ – Yuval Filmus Jan 12 '16 at 14:30
  • $\begingroup$ @user3680510 It can be shown you have up to $2^{c\frac{\log n}{\log\log n}}$ for some fixed $c>0$ and related problem is here mathoverflow.net/questions/222392/…. $\endgroup$ – 1.. Jan 13 '16 at 5:13