# Hardness of 3-Partition with Small Target Value

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 Johnson , 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))$$?

 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.

• Perhaps you can use some padding trick to get from $n^4$ to $\sqrt{n}$. Nov 15 at 21:40
• 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.
Nov 17 at 21:14