# Is this partition problem strongly NP-complete?

The Partition problem is weakly NP-complete: Given a set A of positive integers, can A be partitioned into two disjoint subsets with the same sum?

I'm interested in the hardness of this variant:

Partition problem: Given a set A of positive integers, can A be partitioned into three disjoint subsets with the same sum?

Is this variant strongly NP-complete?

-

No. The pseudo-polynomial dynamic programming algorithm that shows that the "partition into 2 equal-weight subsets" is only weakly NP-hard can be generalized (straightforwardly) to "partition into $k$ equal-weight subsets" for any fixed $k$. The degree of the polynomial will depend on $k$, though.
More precisely, there are at most possible $N^k$ different statements of the form "the first $i$ input numbers can be partitioned into $k-1$ sets with weights $(a_1,a_2,...,a_{k-1})$ plus a (possibly empty) rest set". Put the truth values of these statements into a $k$-dimensional array, and fill it in dynamically by indreasing $i$. This takes $O(N^k)$ time.
Thanks Henning, So I guess if $k= O(\log n)$ then it would not be strongly NP-complete? right? – Mohammad Al-Turkistany Nov 27 '11 at 22:22
@turkistany: That would give the simple algorithm I skech a runtime of $O(n^{\log n})$, and unless I'm missing something that's not actually polynomial. There might still be some other pseudopolynomial algorithm that works for the $k=O(\log n)$ case, of course. – Henning Makholm Nov 27 '11 at 22:38