<p>In the 3-partition problem, we are given a set of positive integers <span class="math-container">$a_1,\ldots,a_n$</span> and a target value <span class="math-container">$T$</span>; the goal is to decide if there is a partition of the numbers to triplets such that the sum of each triplet is exactly <span class="math-container">$T$</span>. In the book of Garey and Johnson [1], it is shown that 3-partition is strongly NP-Hard via a reduction from 3-dimensional matching. However, their result uses instances with <span class="math-container">$T = \Omega(n^4)$</span> (i.e., relatively large target value w.r.t. the number of given numbers).</p>
<p><strong>Question:</strong> Is 3-partition remains NP-Hard if, e.g., <span class="math-container">$T = O(\sqrt{n})$</span> or even <span class="math-container">$T = O(\log(n))$</span>?</p>
<p>[1] Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.</p>

CC BY-SA 4.0
2023-11-15T21:40:36.570Z
Perhaps you can use some padding trick to get from $n^4$ to $\sqrt{n}$.
Yuval Filmus
CC BY-SA 4.0
2023-11-17T21:14:07.780Z
I suggest you review the existing reduction to see if it can be tweaked to generate problem instances where $T-3\min(a_1,\dots,a_n) = O(\sqrt{n})$, and then come back to [edit] the question to show your progress and what is the obstacle to doing that.
D.W.
<np-hardness><np-complete><partition-problem>
Hardness of 3-Partition with Small Target Value
John
# Hardness of 3-Partition with Small Target Value

(Asked by: username_0 on 2023-11-15)

In the 3-partition problem, we are given a set of positive integers $a\_1,\ldots,a\_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum of each triplet is exactly $T$. In the book of Garey and username_0son [1], it is shown that 3-partition is strongly NP-Hard via a reduction from 3-dimensional matching. However, their result uses instances with $T = \Omega(n^4)$ (i.e., relatively large target value w.r.t. the number of given numbers).

**Question:** Is 3-partition remains NP-Hard if, e.g., $T = O(\sqrt{n})$ or even $T = O(\log(n))$?

[1] Garey, Michael R. and David S. username_0son (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.

**Tags:** np-hardness, np-complete, partition-problem

> **Comments:**
> **username_1**: Perhaps you can use some padding trick to get from $n^4$ to $\sqrt{n}$.  
> **username_2**: I suggest you review the existing reduction to see if it can be tweaked to generate problem instances where $T-3\min(a_1,\dots,a_n) = O(\sqrt{n})$, and then come back to [edit] the question to show your progress and what is the obstacle to doing that.  

---

## 0 answers

