2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Perhaps you can use some padding trick to get from $n^4$ to $\sqrt{n}$. $\endgroup$
    – Yuval Filmus
    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

0

Reset to default

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.