Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 8 down vote favorite

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?

share|improve this question

1 Answer

up vote 4 down vote

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.

share|improve this answer
An actual reduction or citation in a journal article would be nice, if possible. – templatetypedef Jan 12 at 20:38
edited .. [take the logs] – AJed Jan 12 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 at 20:42
@templatetypedef .. good point. – AJed Jan 12 at 20:43
1  
@templatetypedef In Garey and Johnson, the reduction is to the exact cover by 3 sets. Due to private communication with Yao. – AJed Jan 12 at 20:59
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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