# 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?

-

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. –  templatetypedef Jan 12 '13 at 20:38
edited .. [take the logs] –  AJed Jan 12 '13 at 20:41
Taking the logs of the numbers doesn't necessarily produce rational numbers, and there would possibly be huge rounding errors. Are you sure you can do this without having to massively blow up the number of bits required to represent the numbers? –  templatetypedef Jan 12 '13 at 20:42
@templatetypedef .. good point. –  AJed Jan 12 '13 at 20:43
@templatetypedef In Garey and Johnson, the reduction is to the exact cover by 3 sets. Due to private communication with Yao. –  AJed Jan 12 '13 at 20:59
show 1 more comment