[Solved]: Is the set-partition problem polynomial time reducible to the subset-sum problem?

Problem Detail: 

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?

Asked By : user1683221

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18159