# Is the "subset product" problem NP-complete?

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?

• 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?) Commented Jun 26, 2014 at 9:44
• @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.
– D.W.
Commented Jun 26, 2014 at 15:12
• @D.W.: Thanks, when I get time I'll do as you suggest! Commented Jun 27, 2014 at 4:47

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.

• +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? Commented Jun 26, 2014 at 9:41
• Excellent point. I've added a paragraph to address that. Commented Jun 26, 2014 at 21:04
• 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. Commented Jun 27, 2014 at 4:46
• Kyle Jones, isn't it critical that step 3 will create a number $k$ of exponential size? Is this reduction really of polynomial time? Commented Aug 21, 2014 at 12:18
• @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)$. Commented Aug 21, 2014 at 18:21

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.

• An actual reduction or citation in a journal article would be nice, if possible. Commented Jan 12, 2013 at 20:38
• @templatetypedef In Garey and Johnson, the reduction is to the exact cover by 3 sets. Due to private communication with Yao.
– AJed
Commented Jan 12, 2013 at 20:59
• 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.) Commented Feb 16, 2019 at 20:40