0
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    @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.2011-11-27