3
$\begingroup$

Consider the following decision problem:

Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers each less than $n^c$ and $t$ is a target natural number, do there exist natural numbers $f_1, \cdots f_n$ such that

  1. $f_i \le b_i$ for all $1 \le i \le n$
  2. $\prod_{i=1}^{n} f_i = t$?

We guess that if the prime factorization of the target $t$ is given, then the problem might be polynomial, and in general, it seems similar to subset-product and might be NP-complete, but we couldn't prove an exact result or find a reference.

Are there any references/results for time complexity of this problem (in the case where the prime factorization of $t$ is given and when it isn't)? If an unpublished solution exists, we'd appreciate a hint!

Improve this question
$\endgroup$
2
  • $\begingroup$ I think it is unlikely that the problem is in P if the factorization of $t$ is given but NP-complete if the factorization is not given, as factoring is considered unlikely to be NP-complete. $\endgroup$
    – D.W. ♦
    Commented Dec 11, 2023 at 0:05
  • $\begingroup$ Since each number $b_i$ is less than $n^c$ and the input size is proportional to $n$, using a naive prime factorization algorithm for $t$, keeps the running time polynomial. So, it is safe to assume that prime factorization is given for $t$. $\endgroup$
    – Inuyasha Yagami
    Commented Dec 11, 2023 at 9:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.