Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.