TOPICS
Search

Number Partitioning Problem


Given a set S of n nonnegative integers, the number partitioning problem requires the division of S into two subsets such that the sums of number in each subset are as close as possible. This problem is known to be NP-complete, but is perhaps "the easiest hard problem" (Hayes 2002; Borwein and Bailey 2003, pp. 38-39).


Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.Hayes, B. "The Easiest Hard Problem." Amer. Sci. 90, 113-117, 2002.Mertens, S. "A Physicist's Approach to Number Partitioning." Theoret. Comput. Sci. 265, 79-108, 2001.

Referenced on Wolfram|Alpha

Number Partitioning Problem

Cite this as:

Weisstein, Eric W. "Number Partitioning Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NumberPartitioningProblem.html

Subject classifications