Partition problem

In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum. More precisely, given a multiset "S" of integers, is there a way to partition "S" into two subsets "S"₁ and "S"₂ such that the sum of the numbers in "S"₁ equals the sum of the numbers in "S"₂? The subsets "S"₁ and "S"₂ must form a partition in the sense that they are disjoint and they cover "S".

The partition problem is equivalent to the following special case of the subset sum problem: given a set "S" of integers, is there a subset "S"₁ of "S" that sums to exactly "t" /2 where "t" is the sum of all elements of "S"? (The equivalence can be seen by defining "S"₂ to be the difference "S" − "S"₁.) Therefore, the pseudo-polynomial time dynamic programming solution to subset sum applies to the partition problem as well.

A variation of the partition problem is the 3-partition problem, in which the set "S" must be partitioned into |"S"|/3 triples each with the same sum. In contrast to partition, 3-partition has no pseudo-polynomial time algorithm unless P = NP: 3-partition remains NP-complete even when using unary coding.

See also

* Subset sum problem
* Bin packing problem

References

* [http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem The Easiest Hard Problem] - article in American Scientist by Brian Hayes.
* [http://arxiv.org/pdf/cond-mat/0310317 The Easiest Hard Problem: Number Partitioning] by Stephan Mertens 2003