3-partition problem
From Wikipedia, the free encyclopedia
The 3-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 triples that all have the same sum. More precisely, given a multiset S of n = 3 m positive integers, can S be partitioned into m subsets S1, S2, …, Sm such that the sum of the numbers in each subset is equal? The subsets S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S. Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains NP-complete when every integer in S is strictly between B/4 and B/2. In this case, each subset Si is forced to consist of exactly three elements (a triple).
The 3-partition problem is similar to the partition problem, which in turn is related to the subset sum problem. In the partition problem, the goal is to partition S into two subsets with equal sum. It is important to note that in 3-partition the goal is to partition S into m subsets (or n/3 subsets), not just three subsets, with equal sum.
[edit] Strong NP-completeness
What is interesting about 3-partition is that it remains NP-complete even when the integers in S are bounded above by a polynomial in n. In other words, the problem remains NP-complete even when representing the numbers in the input instance in unary. In other words, 3-partition is NP-complete in the strong sense or strongly NP-complete. This property, and 3-partition in general, is useful in many reductions where numbers are naturally represented in unary. In contrast, the partition problem is known to be NP-complete only when the numbers are encoded in binary, and have value exponential in n.
[edit] Descriptions
Garey and Johnson (1975) originally proved that 3-partition to be NP-complete, by a reduction from 3-dimensional matching. The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition. The 4-partition problem is an analog of 3-partition in which the goal is to partition a given set S into quadruples all with the same sum: precisely, the difference is that S now consists of n = 4 m integers, each strictly between B/5 and B/3.
[edit] References
- Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.
- Garey, Michael R. and David S. Johnson (1975). "Complexity results for multiprocessor scheduling under resource constraints". SIAM Journal on Computing 4: 397–411.
