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
