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.