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 mpositive integers, can S be partitioned into m triplets S1, S2, …, Sm such that the sum of the numbers in each subset is equal? The subsetsS1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they coverS. Let Bdenote the sum of each subset Si, or equivalently, let the total sum of the numbers in S be mB. The 3-partition problem remains strongly 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, not just two subsets, with equal sum.
Example
The set can be partitioned into the three sets,, each of which sum to 90.
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 non-unary system, and have value exponential in n.
Descriptions
Garey and Johnson originally proved 3-partition to be NP-complete, by a reduction from 3-dimensional matching. The classic reference by Garey and Johnson 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.
