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 S₁, S₂, …, S_m such that the sum of the numbers in each one is equal to T. The S₁, S₂, …, S_m 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 S_u of the unrestricted variant, construct a new instance of the restricted version S_r := {s + 2 T | s in S_u}. Every solution of S_u corresponds to a solution of S_r but with a sum of 7 T instead of T, and every element of S_r 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.^[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 S_u of the restricted variant, construct a new instance of the unrestricted variant S_r := {s + 2 T | s in S_u}, with target sum 7 T. Every solution of S_u naturally corresponds to a solution of S_r. In every solution of S_r, 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 S_u.

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. ^[2] 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.^[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[]