Question Detail: Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don’t see the relation! Is it possible to reduce this problem using a Levin Reduction ? If you don’t understand write for clarification!
Asked By : dbonadiman
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6111
Answered By : Yuval Filmus
Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = sum L$. Let $L’$ be the list formed by adding $S+B,2S-B$ to $L$. (1) If there is a sublist $M subseteq L$ summing to $B$, then $L’$ can be partitioned into two equal parts: $M cup { 2S-B }$ and $Lsetminus M cup { S+B }$. Indeed, the first part sums to $B+(2S-B) = 2S$, and the second to $(S-B)+(S+B) = 2S$. (2) If $L’$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. Indeed, since $(S+B)+(2S-B) = 3S$ and each part sums to $2S$, the two elements belong to different parts. Without loss of generality, $2S-B in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$.
