# Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$$3$$-$$\mathrm{Partition}$$ problem is $$\mathsf{NP}$$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $$\mathsf{P=NP}$$. I am looking for the fastest known exact algorithm that solves $$3$$-$$\mathrm{Partition}$$.

Is there a fast (e.g subexponential) algorithm for $$3$$-$$\mathrm{Partition}$$? Is it possible to solve it faster than using SAT solvers?

• If this does not get a good answer after a few days, it's a candidate for migration to Theoretical Computer Science. – Raphael Mar 26 '13 at 13:01
• @Raphael, Yes I agree, but I didn't search enough but by my knowledge I couldn't find anything, so I said it's better to first ask it here. – user742 Mar 26 '13 at 13:23
• Clearly you need to go with an approximation algorithm and it will have to be at best a PTAS (if that is achievable). I have not come across any specific approximations for 3-partition, but if you would like to construct your own, there are a couple of standard tricks you could use to construct it (works for any kind of approximation) -- (1) Take the DP solution and approximate the state-space down to some polynomial size, or (2) Perform input rounding so that the inputs produce a polynomial size state-space, or (3) a combination of (1) and (2). It would be cool to see what bounds you get. – RDN Mar 26 '13 at 19:32
• @RDN, First I'm not looking for apprximation, approximation is another problem, second, I cannot see how DP is helpful, I strongly mentioned this is strong NP-Compelete, I don't think you could find any good DP for this (except converting to bin packing and allowing 3 item per bin, which is not really DP). – user742 Mar 27 '13 at 9:16
• @RDN Note that "subexponential" is not (strictly) the same as "polynomial", see here. I guess Saeed would also be interested in an algorithm that runs in time, say, $O(1.1^n)$. – Raphael Mar 27 '13 at 12:09

## 1 Answer

If you find a fast (sub-exponential) exact algorithm for 3-Partition , while 3-Partition is NP-Complete, then dear sir you have just proven P=NP, which no body has done so far, and you have a 1M \$ price waiting for you as well as wealth and fame, cheers.

Anyway if you do have a faster than a SAT solver, wouldn't you actually be performing SAT it's self faster? I mean if you can reduce SAT to 3-PARTITION and you can solve 3-PARTITION in sub-expo time, doesn't that mean that SAT can be solved in sub-expo time, hence all NP-COMPLETE problems also can be solved in such time? So you might as well be looking for a sub-expo time solution of any other NP-COMPLETE problem just as well, it would still be a significant breakthrough.

• – xskxzr Mar 11 '18 at 4:57
• @xskxzr: as has been commented almost five years ago. – greybeard Mar 11 '18 at 11:23