TOPICS
Search

Subset Product Problem

The subset product problem asks whether, for given positive integers a_1,...,a_n and a target positive integer t, there is a subset S subset= {1,...,n} such that

product_(i in S)a_i=t.

It is the multiplicative analog of the given-sum version of the subset sum problem. The decision problem is NP-complete, even though a dynamic programming algorithm runs in pseudopolynomial time in the numerical value of t.

The reduction from the exact cover problem restricted to 3-sets establishing NP-completeness is credited to Andrew C. Yao in a 1978 private communication (Garey and Johnson 1979, pp. 224 and 325).

See also

NP-Complete Problem, Subset, Subset Sum Problem

Explore with Wolfram|Alpha

References

Dutta, P. and Rajasree, M. S. "Efficient Reductions and Algorithms for Variants of Subset Sum." 21 Dec 2021. https://arxiv.org/abs/2112.11020.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 224-225 and 325, 1979.

Cite this as:

Weisstein, Eric W. "Subset Product Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SubsetProductProblem.html

Subject classifications