20
$\begingroup$

The subset-sum problem is a classic NP-complete problem:

Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$?

A student asked me if this variant of the problem called the "subset product" problem is NP-complete:

Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

I did some searching and couldn't find any resources that talked about this problem, though perhaps I missed them.

Is the subset product problem NP-complete?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Interesting answers, but I'm wondering: Can't we reduce to Subset Sum just by taking logs of k and all the numbers? (Maybe I should ask a separate question?) $\endgroup$ – j_random_hacker Jun 26 '14 at 9:44
  • 1
    $\begingroup$ @j_random_hacker, yes, if you cannot find an answer after searching on this site and online, I suggest you post a separate question. It is a nice question with a nice answer (hint: taking logs leaves you with something that isn't an integer; in the other direction, think about what exponentiating does to the size of the numbers), but it's a bit of a tangent and would be better in its own question. $\endgroup$ – D.W.♦ Jun 26 '14 at 15:12
  • 1
    $\begingroup$ @D.W.: Thanks, when I get time I'll do as you suggest! $\endgroup$ – j_random_hacker Jun 27 '14 at 4:47
13
$\begingroup$

A comment mentions a reduction from X3C to SUBSET PRODUCT attributed to Yao. Given the target of the reduction it wasn't hard to guess what the reduction was likely to have been.

Definitions:

EXACT COVER BY 3-SETS (X3C)

Given a finite set $X$ with $|X|$ a multiple of 3, and a collection $C$ of 3-element subsets of $X$, does $C$ contain an exact cover $C'$ for $X$, where $C' \subseteq C$ and every element in $X$ occurs in exactly once in $C'$?

SUBSET PRODUCT

Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

To reduce an X3C instance to a SUBSET PRODUCT instance:

  1. Establish a bijective mapping between the members of $X$ and the first $|X|$ prime numbers. Replace the members of $X$ and the $C$ subsets with the mapped primes.

  2. For each subset in $C$, multiply its members together; the resulting list of products is $L$ for the SUBSET PRODUCT instance. Because prime numbers are used for the mapping in step 1, the products are guaranteed to be equivalent iff the subsets are equivalent by the unique factorization theorem.

  3. Multiply the members of $X$ together; the resulting product is the value $k$ for the SUBSET PRODUCT instance.

The prime factors of $k$ are exactly the members of $X$. The prime factors of the numbers in $L$ correspond exactly to the members of the $C$ subsets. Therefore any solution to the new SUBSET PRODUCT instance can be transformed into a X3C solution by mapping the solution members of $L$ back to the subsets in $C$.

Each of the 3 transformation steps involves operations that are polynomial to the size of the input $|X|$ or the size of a member of $X$. The first $|X|$ primes can be generated in time O($|X|$) using the sieve of Eratosthenes and are guaranteed to fit into $O(|X|^2 \ln |X|)$ space by the prime number theorem.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ +1, but for the reduction to go through I think we require that the first |X| prime numbers can be represented in a number of bits that is polynomial in |X| -- am I right about this, and if so, do we have that guarantee? $\endgroup$ – j_random_hacker Jun 26 '14 at 9:41
  • 1
    $\begingroup$ Excellent point. I've added a paragraph to address that. $\endgroup$ – Kyle Jones Jun 26 '14 at 21:04
  • 1
    $\begingroup$ Thanks, that theorem cements it! Not to nitpick, but according to the page you linked to, the kth prime number is approximately k log k, and given that the Sieve of Eratosthenes apparently calculates all primes up to n in time O(n log log n), substituting n = k log k appears to give a time of O(k*log(k)*log(log(k log k))), rather than O(k) (your O(|X|)), to calculate the first k primes that way. $\endgroup$ – j_random_hacker Jun 27 '14 at 4:46
  • 1
    $\begingroup$ Kyle Jones, isn't it critical that step 3 will create a number $k$ of exponential size? Is this reduction really of polynomial time? $\endgroup$ – user1742364 Aug 21 '14 at 12:18
  • 3
    $\begingroup$ @user1742364 No, because computing $k$ doesn't require an exponential number of operations or require storing an exponential number of bits. Computing $k$ requires $|X|$ multiplications and multiplication is at worst a $O(n^2)$ operation. While $k$ will be exponentially larger than the largest prime $P$ in $X$, the number of bits needed to store $k$ will be $O(\log P)$. $\endgroup$ – Kyle Jones Aug 21 '14 at 18:21
9
$\begingroup$

According to [1]: Yes it is

I also cite the same reference: Comments: There is a subtle technical distinction between this and Problem 42: the former case has a pseudo-efficient algorithm obtained by allowing numbers to be represented in unary; unless all NP-complete problems can be solved by fast algorithms, however, the Subset Product Problem, cannot be solved by `efficient' methods using even this unreasonable input representation.

have a look on [2] for a reduction. [2]: Fellows, Michael, and Neal Koblitz. "Fixed-parameter complexity and cryptography." Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (1993): 121-131.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ An actual reduction or citation in a journal article would be nice, if possible. $\endgroup$ – templatetypedef Jan 12 '13 at 20:38
  • 3
    $\begingroup$ @templatetypedef In Garey and Johnson, the reduction is to the exact cover by 3 sets. Due to private communication with Yao. $\endgroup$ – AJed Jan 12 '13 at 20:59
  • $\begingroup$ The reduction in the cryptography paper is for a different problem, in which the target product is replaced by congruence with a target number modulo a modulus given in the instance. (Though if I understand the proof correctly, they only get weak hardness anyway because the modulus is exponential in magnitude.) $\endgroup$ – Jeffrey Bosboom Feb 16 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.