<p>After reading this post <a href="https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring">An NP-complete variant of factoring.</a> I come up with a question.</p>

<p>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.</p>

<p>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$.</p>

<p>Wouldn't this make Factoring also NP-complete?</p>

CC BY-SA 3.0
2016-01-12T08:06:13.060Z
i think the error is that there a exponentiell number of products, since it is $n$.
user3680510
CC BY-SA 3.0
2016-01-12T14:30:46.150Z
It seems you answered your own question.
Yuval Filmus
CC BY-SA 3.0
2016-01-13T05:13:12.930Z
@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 http://mathoverflow.net/questions/222392/on-variant-of-integer-factorization.
Turbo
<np><np-complete><factoring>
An NP-complete variant of factoring and relation to factoring
user3680510
# An NP-complete variant of factoring and relation to factoring

(Asked by: username_0 on 2016-01-12)

After reading this post [An NP-complete variant of factoring.](https://cstheory.stackexchange.com/questions/4769/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?

**Tags:** np, np-complete, factoring

> **Comments:**
> **username_0**: i think the error is that there a exponentiell number of products, since it is $n$.  
> **username_1**: It seems you answered your own question.  
> **username_2**: @username_0 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 http://mathoverflow.net/questions/222392/on-variant-of-integer-factorization.  

---

## 0 answers

