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 [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. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.