3
$\begingroup$

There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint presentation (slide 12), where it says that the inverse is also true. i.e. the set-partition problem is polynomial time reducible to the subset-sum problem. So far, I have been unable to find any proofs to show the same.

So, my question: How is the set-partition problem polynomial time reducible to the subset-sum problem, or was there an error on the presentation above?

$\endgroup$
3
$\begingroup$

First, both problems are NP-complete, and are therefore reducible to each other. A concrete reduction can go through the Cook-Levin theorem (i.e. SET-PARTITION$\le_p$SAT$\le_p$SUBSET-SUM).

However, in this case there is a fairly trivial direct reduction: given an instance $\{x_1,...,x_n\}$ for SET-PARTITION, compute $t=\sum_{i=1}^n x_i$ and output $\{x_1,...,x_n\},t/2$ as input for SUBSET-SUM. The correctness of this is very easy to show.

$\endgroup$

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.