<p>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 &lt; a_i &lt; B/2$ are not imposed in [1], but this should not make a difference.</p>

<p>[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Oper. Res. Lett. 36(5): 594-596 (2008). <a href="http://dx.doi.org/10.1016/j.orl.2008.05.004">DOI</a></p>

CC BY-SA 2.5
2010-08-30T01:14:03.280Z
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
CC BY-SA 2.5
2010-08-30T02:37:12.657Z
Indeed, it is straightforward to also impose these bounds.
Serge Gaspers
CC BY-SA 2.5
2010-08-30T12:31:18.670Z
Thanks, it answers my question completely.  Note that the partial Latin square completion problem can be easily formulated as a special case of the 3-dimensional matching.  It did not occur to me to replace 3DM by PLSC, but after seeing the proof, the approach seems quite natural.
Tsuyoshi Ito
CC BY-SA 2.5
2010-08-30T00:35:53.567Z
2010-08-30T00:35:53.567Z
Serge Gaspers
<p>This question is related to an <a href="https://cstheory.stackexchange.com/questions/709/what-complexity-class-does-the-cutting-sticks-problem-belong-to/713#713">answer</a> I posted in response to another question.</p>

<p>The 3-partition problem is the following problem:<br>
<em>Instance</em>: Positive integers a<sub>1</sub>, …, a<sub>n</sub>, where n=3m and the sum of the n integers is equal to mB, such that each a<sub>i</sub> satisfies B/4 &lt; a<sub>i</sub> &lt; B/2.<br>
<em>Question</em>: Can the integers a<sub>1</sub>, …, a<sub>n</sub> be partitioned into m multisets so that the sum of each multiset is equal to B?</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness" rel="noreferrer">Garey and Johnson</a> for a proof.</p>

<p><strong>Questions</strong>: Does the 3-partition problem remain NP-complete if the numbers a<sub>1</sub>, …, a<sub>n</sub> are all distinct?  Does it remain NP-complete in the strong sense?</p>

<p>(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.)</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-08-29T19:18:10.227Z
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
<cc.complexity-theory><np-hardness>
Computational complexity of the 3-partition problem with distinct numbers
Tsuyoshi Ito
# Computational complexity of the 3-partition problem with distinct numbers

(Asked by: username_0 on 2010-08-28)

This question is related to an [answer](https://cstheory.stackexchange.com/questions/709/what-complexity-class-does-the-cutting-sticks-problem-belong-to/713#713) 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](http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness) 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.

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2010-08-30. Score: 22 | Accepted answer

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.

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Oper. Res. Lett. 36(5): 594-596 (2008). [DOI](http://dx.doi.org/10.1016/j.orl.2008.05.004)

> **Comments:**
> **username_1**: Imposing the bounds $B/4 < a_i < B/2$ is easily done by adding the same large number to all of the $a_i$.  
> **username_2**: Indeed, it is straightforward to also impose these bounds.  
> **username_0**: Thanks, it answers my question completely.  Note that the partial Latin square completion problem can be easily formulated as a special case of the 3-dimensional matching.  It did not occur to me to replace 3DM by PLSC, but after seeing the proof, the approach seems quite natural.  

---

