2
$\begingroup$

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 $S_1$ of set $S$ so that it sums to a number $t$ and in set partition problem we need to find a subset $X_1$ of set $X$ such that summation of numbers in set $X_1$ is half of that in $X$.

So let us take instance of subset sum problem where $t = (\text{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 is 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.

$\endgroup$

1 Answer 1

1
$\begingroup$

No, your can't arbitrarily choose $t$ so your proof is incorrect.

In fact, you have build a reduction from the following variant of subset sum problem to partition problem:

Given a set $S$ of integers whose sum is $s$, is there a subset of $S$ whose sum is $s/2$?

This variant is different from the normal subset problem, and you cannot assert it is NP-complete (though it in fact is), so your proof is incorrect.

You can find a complete proof here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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