# Computational complexity of the 3-partition problem with distinct numbers

This question is related to an answer I posted in response to another question.

The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.
Question: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

It is well-known that the 3-partition problem is NP-complete in the strong sense that it remains NP-complete even if the numbers in the input are given in unary. See Garey and Johnson for a proof.

Questions: Does the 3-partition problem remain NP-complete if the numbers a1, …, an are all distinct? Does it remain NP-complete in the strong sense?

(My feeling is that the answers to both questions are probably yes because I do not see any reason why the problem should become easier if all numbers are distinct.)

It does not seem that the proof in Garey and Johnson establishes the NP-completeness of this restricted version.

In the answer to the other question linked above, I gave a proof that the 6-partition problem (defined analogously) with distinct numbers is NP-complete in the strong sense.

• I think this is an important problem; I found several papers in the literature that state or assume that the set version is hard, with no better justification than a citation to the multiset version in Garey and Johnson, and that use that assumption in a claim of NP-completeness for some other problem. – David Eppstein Aug 29 '10 at 19:18

It is proved in [1, Corollary 7], that 3-partition is strongly NP-hard when the integers $a_1, \ldots, a_n$ are all distinct. The bounds $B/4 < a_i < B/2$ are not imposed in [1], but this should not make a difference.
• Imposing the bounds $B/4 < a_i < B/2$ is easily done by adding the same large number to all of the $a_i$. – David Eppstein Aug 30 '10 at 1:14