<p>Consider the following factoring problem:</p>
<p>Given an integer <span class="math-container">$r$</span> and another integer <span class="math-container">$N$</span> along with all of its <span class="math-container">$n$</span> number of prime factors and their corresponding multiplicities <span class="math-container">$\{p_i,e_i\}_{i=1}^n$</span>, is there a partition of the prime factors and their multiplicities to <span class="math-container">$\{p_i,g_i\}_{i=1}^n$</span> and <span class="math-container">$\{p_i,h_i\}_{i=1}^n$</span> where at every <span class="math-container">$i$</span> we have <span class="math-container">$e_i=g_i+h_i$</span> and <span class="math-container">$g_i,h_i\geq0$</span> holds such that <span class="math-container">$$\Bigg|\prod_{i=1}^np_i^{g_i}-\prod_{i=1}^np_i^{h_i}\Bigg|&lt;r?$$</span></p>
<p>The problem is clearly in <span class="math-container">$NP$</span> and might be in <span class="math-container">$PromiseUP$</span> for small enough <span class="math-container">$r$</span> depending on <span class="math-container">$N$</span> (if there exist a <span class="math-container">$PTIME$</span> computable <span class="math-container">$r_{min}$</span> depending on <span class="math-container">$N$</span> then the problem is in <span class="math-container">$P$</span>). Is it <span class="math-container">$NP$</span>-hard or is it in <span class="math-container">$coNP$</span> or is it in <span class="math-container">$P$</span>?</p>
<p><strong>Update</strong> It appears from comments that I am looking for the factor closest to <span class="math-container">$\sqrt{N}$</span> when the list of prime factors dividing <span class="math-container">$N$</span> is given. Is this problem <span class="math-container">$NP$</span>-hard?</p>
<p>Seems similar to finding a split a given multiset of integers to two complementary submultisets (intersection is empty while union is whole) whose respective sums are close to each other. This subset sum problem might be <span class="math-container">$NP$</span>-complete as it is similar to <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Partition_problem</a>.</p>

CC BY-SA 4.0
2022-04-12T19:53:49.167Z
A nontrivial result of which I've lost the source is that numbers can have a super-polynomial number of divisors, so simply enumerating the divisors won't bring a polynomial algorithm. (As an anecdote, many years ago I went to a physical library to find that result.)
Albert Hendriks
CC BY-SA 4.0
2022-04-13T05:29:39.213Z
Stated more simply, you are asking if there is a divisor $M\mid N$ such that $|M-N/M|<r$. This quantity is minimized near $\sqrt N$ (and it is essentially linear in $|M-\sqrt N|$), thus the problem is equivalent to: given $N$ along with its prime factorization, compute the divisor $M\mid N$ which is closest to $\sqrt N$.
Emil Jeřábek
CC BY-SA 4.0
2022-04-13T05:52:10.870Z
That is, it is poly-time many-one equivalent to the decision problem given $N$ with its factorization and $r$, determine if there is $M\mid N$ such that $|M-\sqrt N|<r$. It is poly-time Turing equivalent to the search problem given $N$ as above, find the divisor of $N$ closest to $\sqrt N$.
Emil Jeřábek
CC BY-SA 4.0
2022-04-13T05:58:07.047Z
@AlbertHendriks That much is obvious: if $N$ is a primorial, it has $N^{(1+o(1))/\log\log N}$ divisors, which is exponential in $\log N$. The somewhat nontrivial result is that this bound is essentially tight.
Emil Jeřábek
CC BY-SA 4.0
2022-04-15T12:08:10.063Z
Closely related to https://cstheory.stackexchange.com/a/4785/13245, not sure if it's an exact duplicate.
Geoffrey Irving
<cc.complexity-theory><np-complete><nt.number-theory><factoring><subset-sum>
Is the following equitable factoring problem $NP$-hard or in $P$?
Turbo
# Is the following equitable factoring problem $NP$-hard or in $P$?

(Asked by: username_0 on 2022-04-12)

Consider the following factoring problem:

Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p\_i,e\_i\}\_{i=1}^n$, is there a partition of the prime factors and their multiplicities to $\{p\_i,g\_i\}\_{i=1}^n$ and $\{p\_i,h\_i\}\_{i=1}^n$ where at every $i$ we have $e\_i=g\_i+h\_i$ and $g\_i,h\_i\geq0$ holds such that $$\Bigg|\prod\_{i=1}^np\_i^{g\_i}-\prod\_{i=1}^np\_i^{h\_i}\Bigg|

The problem is clearly in $NP$ and might be in $PromiseUP$ for small enough $r$ depending on $N$ (if there exist a $PTIME$ computable $r\_{min}$ depending on $N$ then the problem is in $P$). Is it $NP$-hard or is it in $coNP$ or is it in $P$?

**Update** It appears from comments that I am looking for the factor closest to $\sqrt{N}$ when the list of prime factors dividing $N$ is given. Is this problem $NP$-hard?

Seems similar to finding a split a given multiset of integers to two complementary submultisets (intersection is empty while union is whole) whose respective sums are close to each other. This subset sum problem might be $NP$-complete as it is similar to <https://en.wikipedia.org/wiki/Partition_problem>.

**Tags:** cc.complexity-theory, np-complete, nt.number-theory, factoring, subset-sum

> **Comments:**
> **username_1**: A nontrivial result of which I've lost the source is that numbers can have a super-polynomial number of divisors, so simply enumerating the divisors won't bring a polynomial algorithm. (As an anecdote, many years ago I went to a physical library to find that result.)  
> **username_2**: Stated more simply, you are asking if there is a divisor $M\mid N$ such that $|M-N/M|<r$. This quantity is minimized near $\sqrt N$ (and it is essentially linear in $|M-\sqrt N|$), thus the problem is equivalent to: given $N$ along with its prime factorization, compute the divisor $M\mid N$ which is closest to $\sqrt N$.  
> **username_2**: That is, it is poly-time many-one equivalent to the decision problem given $N$ with its factorization and $r$, determine if there is $M\mid N$ such that $|M-\sqrt N|<r$. It is poly-time Turing equivalent to the search problem given $N$ as above, find the divisor of $N$ closest to $\sqrt N$.  
> **username_2**: @AlbertHendriks That much is obvious: if $N$ is a primorial, it has $N^{(1+o(1))/\log\log N}$ divisors, which is exponential in $\log N$. The somewhat nontrivial result is that this bound is essentially tight.  
> **username_3**: Closely related to https://cstheory.stackexchange.com/a/4785/13245, not sure if it's an exact duplicate.  

---

## 0 answers

