Partition problem

From Wikipedia, the free encyclopedia

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.

[edit] See also

• Subset sum problem
• Bin packing problem

[edit] References

• The Easiest Hard Problem - article in American Scientist by Brian Hayes.
• The Easiest Hard Problem: Number Partitioning by Stephan Mertens 2003