3-partition problem
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 triplets 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.
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. In 3-partition the goal is to partition S into m subsets (or n/3 subsets), not just two subsets, with equal sum.
Example
The set { 20, 23, 25, 45, 27, 40 } can be partitioned into the two sets { 20, 25, 45 }, { 23, 27, 40 }, each of which sum to 90.
Strong NP-completeness
The 3-partition problem 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. i.e., 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.
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.
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 (4): 397–411. doi:10.1137/0204035.