3

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|<r?$$

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.

Turbo
  • 12,812
  • 1
  • 19
  • 68
  • 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 Apr 12 '22 at 19:53
  • 1
    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 Apr 13 '22 at 05:29
  • 1
    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 Apr 13 '22 at 05:52
  • @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 Apr 13 '22 at 05:58
  • 1
    Closely related to https://cstheory.stackexchange.com/a/4785/13245, not sure if it's an exact duplicate. – Geoffrey Irving Apr 15 '22 at 12:08

0 Answers0