Take the 2-minute tour ×
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.

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

2 Answers 2

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.

share|improve this answer
    
+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? –  j_random_hacker Jun 26 at 9:41
    
Excellent point. I've added a paragraph to address that. –  Kyle Jones Jun 26 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. –  j_random_hacker Jun 27 at 4:46

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 '13 at 20:38
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 '13 at 20:59

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.