# 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 m T.
• 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

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 sum to T = 90. Another example; 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.

## 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 in 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 (7 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 T | s in 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 (7 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 m T, 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 m T. 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.