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

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 $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 $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.  This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers 1000a+100 for each $a\in A$ ; 1000b+10 for each $b\in B$ ; and 1000c+1 for each $c\in C$ . Every solution of the ABC-partition instance induces a solution of the 3-partition instance with sum $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 $A,B,C$ , where there is an hyperedge $(a,b,c)$ for every three vertices in $A,B,C$ such that $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. The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.

## Applications

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