Partition problem

From Wikipedia, the free encyclopedia

The partition problem is an NP-complete problem in computer science. 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 sums of the numbers in each subset are equal? 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 if the numbers are encoded in unary.

[edit] See also

• Subset sum problem
• Bin packing problem

[edit] References

• The Easiest Hard Problem - article in American Scientist by Brian Hayes.
• Bhattacharyya, M., "A Hybrid Algorithm using Genetic Adaptive Systems and Heuristics for Partition Problem", Proceedings of the International Conference on Intelligent Systems and Networks, Haryana, India, 2007, pp. 184-189.