There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete?

Solution: I can prove that it belongs to NP but I am not able to find a reduction from another NP complete problem to this problem. I have tried reducing Subset Partition problem to this problem but no luck.

Please suggest any alternate solutions or how to reduce from Subset Partition to this problem.

  • 1
    $\begingroup$ What have you tried and where did you get stuck? Hint: Imagine the problem statement was "... of both sets is 0". What then? $\endgroup$ – Raphael Dec 1 '14 at 13:04
  • $\begingroup$ @Raphael, I am not able to find a reduction from another NP Complete problem to this problem. That's where I am stuck. $\endgroup$ – alchemist Dec 2 '14 at 1:48

Hint: Multiply all the numbers in the set by a factor of 100. What happens? What if you multiply them by a factor of 1000?

This should be enough to help you find the reduction you want.

  • $\begingroup$ So, if xi is the set of elements for Subset Partition (SP) problem and yi is the set of elements for this problem then I should reduce SP to this as: yi = 1000* xi , so if SP has a solution then this problem will also have a solution but how does multiplying by 100 or 1000 makes sure that if the difference between the partition sets is atmost 100 then also we should get a solution? Could you please elaborate this reduction with an example. Thanks $\endgroup$ – alchemist Dec 1 '14 at 7:24
  • $\begingroup$ If there is a solution for the yi's where the difference is at most 100, then what does that mean for the original problem? Remember we can get the xi's back by dividing by 1000. $\endgroup$ – Tom van der Zanden Dec 1 '14 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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