Is the "subset product" problem NP-complete?

Problem Detail: 

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?

Asked By : templatetypedef

Answered By : Kyle Jones

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7907