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 is pseudopolynomial in the numerical value of t.

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, p. 225, 1979.

Cite this as:

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

Subject classifications