# 3-partition problem

The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:

• The input to the problem is a multiset S of n = 3 m  positive integers. The sum of all integers is ${\displaystyle mT}$.
• The output is whether or not there exists a partition of S into m triplets S1, S2, …, Sm such that the sum of the numbers in each one is equal to T. The S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S.

The 3-partition problem remains strongly NP-complete under the restriction that every integer in S is strictly between T/4 and T/2.

## Example

1. The set ${\displaystyle S=\{20,23,25,30,49,45,27,30,30,40,22,19\}}$ can be partitioned into the four sets ${\displaystyle \{20,25,45\},\{23,27,40\},\{49,22,19\},\{30,30,30\}}$, each of which sums to T = 90.
2. The set ${\displaystyle S=\{1,2,5,6,7,9\}}$ can be partitioned into the two sets ${\displaystyle \{1,5,9\},\{2,6,7\}}$ each of which sum to T = 15.
3. (every integer in S is strictly between T/4 and T/2): ${\displaystyle S=\{4,5,5,5,5,6\}}$, thus m=2, and T=15. There is feasible 3-partition ${\displaystyle \{4,5,6\},\{5,5,5\}}$.
4. (every integer in S is strictly between T/4 and T/2): ${\displaystyle S=\{4,4,4,6,6,6\}}$, thus m=2, and T=15. There is no feasible solution.

## 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.

## 3-Partition vs Partition

The 3-partition problem is similar to the partition problem, in which the goal is to partition S into two subsets with equal sum, and the multiway number partitioning, in which the goal is to partition S into k subsets with equal sum, where k is a fixed parameter. In 3-Partition the goal is to partition S into m = n/3 subsets, not just a fixed number of subsets, with equal sum. Partition is "easier" than 3-Partition: while 3-Partition is strongly NP-hard, Partition is only weakly NP-hard - it is hard only when the numbers are encoded in non-unary system, and have value exponential in n. When the values are polynomial in n, Partition can be solved in polynomial time using the pseudopolynomial time number partitioning algorithm.

## Variants

In the unrestricted-input variant, the inputs can be arbitrary integers; in the restricted-input variant, the inputs must be in (T/4, T/2). The restricted version is as hard as the unrestricted version: given an instance Su of the unrestricted variant, construct a new instance of the restricted version Sr ≔ {s + 2 T  | s ∈ Su}. Every solution of Su corresponds to a solution of Sr but with a sum of 7 T  instead of T, and every element of Sr is in [2 T , 3 T ] which is contained in (T /4, 7 T /2).

In the distinct-input variant, the inputs must be in (T/4, T/2), and in addition, they must all be distinct integers. It, too, is as hard as the unrestricted version.[1]

In the unrestricted-output variant, the m output subsets can be of arbitrary size - not necessarily 3 (but they still need to have the same sum T). The restricted-output variant can be reduced to the unrestricted-variant: given an instance Su of the restricted variant, construct a new instance of the unrestricted variant Sr ≔ {s + 2{{hsp|T}} | s ∈ Su}, with target sum 7 T . Every solution of Su naturally corresponds to a solution of Sr. In every solution of Sr, since the target sum is 7 T  and each element is in (T /4, 7 T /2), there must be exactly 3 elements per set, so it corresponds to a solution of Su.

The 4-partition problem is a variant in which S contains n = 4 m  integers, the sum of all integers is ${\displaystyle mT}$, and the goal is to partition it into m quadruples, all with a sum of T. It can be assumed that each integer is strictly between T/5 and T/3.

The ABC-partition problem is a variant in which, instead of a set S with 3 m  integers, there are three sets A, B, C with m integers in each. The sum of numbers in all sets is ${\displaystyle mT}$. The goal is to construct m triplets, each of which contains one element from A, one from B and one from C, such that the sum of each triplet is T. [2] This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers 1000a+100 for each ${\displaystyle a\in A}$; 1000b+10 for each ${\displaystyle b\in B}$; and 1000c+1 for each ${\displaystyle c\in C}$. Every solution of the ABC-partition instance induces a solution of the 3-partition instance with sum ${\displaystyle 1000(a+b+c)+111=1000T+111}$. Conversely, in every solution of the 3-partition instance, all triplet-sums must have the same hundreds, tens and units digits, which means that they must have exactly 1 in each of these digits. Therefore, each triplet must have exactly one number of the form 1000a+100, one 1000b+10 and one 1000c+1. Hence, it induces a solution to the ABC-partition instance.

• The ABC-partition problem is also called numerical 3-d matching, as it can also be reduced to the 3-dimensional matching problem: given an instance of ABC-partition, construct a tripartite hypergraph with sides ${\displaystyle A,B,C}$, where there is an hyperedge ${\displaystyle (a,b,c)}$ for every three vertices in ${\displaystyle A,B,C}$ such that ${\displaystyle a+b+c=T}$. A matching in this hypergraph corresponds to a solution to ABC-partition.

## Proofs

Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from 3-dimensional matching.[3] The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.[4]

## Applications

The NP-hardness of 3-partition was used to prove the NP-hardness rectangle packing, as well as of Tetris[5][6] and some other puzzles,[7] and some job scheduling problems.[8]

## References

1. ^ Hulett, Heather; Will, Todd G.; Woeginger, Gerhard J. (2008-09-01). "Multigraph realizations of degree sequences: Maximization is easy, minimization is hard". Operations Research Letters. 36 (5): 594–596. doi:10.1016/j.orl.2008.05.004. ISSN 0167-6377.
2. ^ Demaine, Erik (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I". Youtube. Archived from the original on 2021-12-14.
3. ^ 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.
4. ^ 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.
5. ^ "Tetris is hard, even to approximate". Nature. 2002-10-28. doi:10.1038/news021021-9. ISSN 0028-0836.
6. ^ BREUKELAAR, RON; DEMAINE, ERIK D.; HOHENBERGER, SUSAN; HOOGEBOOM, HENDRIK JAN; KOSTERS, WALTER A.; LIBEN-NOWELL, DAVID (2004-04-01). "Tetris is Hard, Even to Approximate". International Journal of Computational Geometry & Applications. 14 (1n02): 41–68. arXiv:cs/0210020. doi:10.1142/s0218195904001354. ISSN 0218-1959. S2CID 1177.
7. ^ Demaine, Erik D.; Demaine, Martin L. (2007-06-01). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23 (S1): 195–208. doi:10.1007/s00373-007-0713-4. ISSN 0911-0119. S2CID 17190810.
8. ^ Bernstein, D.; Rodeh, M.; Gertner, I. (1989). "On the complexity of scheduling problems for parallel/pipelined machines". IEEE Transactions on Computers. 38 (9): 1308–1313. doi:10.1109/12.29469. ISSN 0018-9340.