Search code examples
subset-sumnp-complete

Proof of NP Completeness of set-partition problem


I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help.
MY METHOD:
In subset sum problem we have to find a subset S1 of set S so that it sums to a number t and in set partition problem we need to find a subset X1 of set X such that summation of numbers in set X1 is half of that in X. So let us take instance of subset sum problem where t = sum of numbers in X / 2. If we can solve the set partition problem than we solved the subset sum problem too. But we know that subset sum id NP Complete so subset sum problem is also NP Complete( I know how to prove it is NP).
I am having doubt whether we can make a choice of t like that or not. Please help.


Solution

  • Your logic is sound, that is a valid reduction.

    We know this is valid because the proof is for the known problem to the unknown problem. You need to prove that EVERY instance of the known problem can be reduced into SOME instance of the unknown problem. So putting restrictions on your unknown problem is perfectly acceptable.

    Some notes: Your description is not sufficient for a proper proof. You noted that you knew this but for any readers here: to prove a problem is NP-Complete, you first prove it is in NP, and then you prove it is NP-Hard. This question only addresses a small portion of what an NP-Hard proof should contain.