How can I reduce Subset Sum to Partition?

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!

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 $L\setminus 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$.

• But the standard subset-sum problem uses all integers, and partition problem uses just non-negative integers... Apr 19 '13 at 17:40
• SUBSET-SUM is NP-complete even with non-negative integers, for example the reduction from 3SAT ends up with non-negative integers. Also, there is probably a direct reduction from integer SUBSET-SUM to non-negative integer SUBSET-SUM. Apr 19 '13 at 20:26
• Yes, I know, and this reduction is very easy. Just noting that it isn't the subset sum in it's "default" form. :) Apr 20 '13 at 3:11
• Would it also work if $L^{'}$ is $L \bigcup \{B, S-B\}$? as $|\{B, S-B\}| = B$, like $|L| = B$ Feb 28 '14 at 17:42
• @Issam It wouldn't, this the PARTITION instance would always have the solution $L,\{B,S-B\}$. Feb 28 '14 at 21:48

The answer mentioned by @Yuval Filmus is incorrect (it's correct ONLY if there are no negative integers). Consider the following multiset :

$$\{-5, 2, 2, 2, 2, 2\}$$

and the target sum is $-2$. We know that there is no subset. Now, we construct the instance for the partition problem. The two new elements added are $2\sigma-t = 12$ and $\sigma+t = 3$. The multiset is now: $$\{-5, 2, 2, 2, 2, 2, 3, 12\}$$ and the total sum is $20$.

The partition problem solves the answer giving the subset $$\{2, 2, 2, 2, 2\}$$ Here, the 2 new elements are in the same subset (there is no other way to partition into half the sum). Hence, this is a counter example. The correct answer is as follows:

Add an element whose value is $2t-\sigma$. The total sum of the multiset is now $2t$. Solve the partition problem which will give 2 subsets of sum $t$. Only one of the partition will contain the new element. We choose the other partition whose sum is $t$ and we have solved the subset problem by reducing it into a partition problem. This is what the link explains.

• But, as Yuval says in a comment to his answer, subset sum is NP-complete even if we restrict to positive integers. So we can assume that there are no negative numbers. Apr 15 '17 at 14:13
• Yes, I agree, subset sum is NP-complete even in case of positive integers. I was just providing a more complete proof for any integer. Apr 15 '17 at 15:31
• "Just providing a more complete proof" and also wrongly claiming that an existing answer is incorrect. Apr 15 '17 at 16:33
• It's incorrect in the sense that it does not work for negative integers. :) Peace :) Apr 15 '17 at 16:43

Here is a straightforward proof:

It is easy to see that SET-PARTITION can be verified in polynomial time; given a partition $$P_1,P_2$$ just sum the two and verify that their sums equal each other, which is obviously a polynomial time verification (because summation is a polynomial operation and we are only performing at most $$|X|$$ many summations).

The core of the proof is in reducing SUBSETSUM to PARTITION; to that end given set $$X$$ and a value $$t$$ (the subset sum query) we form a new set $$X'=X \cup \{s-2t\}$$ where $$s=\sum_{x \in X}x$$. To see that this is a reduction:

• ($$\implies$$ ) assume there exists some $$S \subset X$$ such that $$t=\sum_{x \in S}x$$ then we would have that $$\begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*}$$ $$\begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*}$$ and we would have that $$S\cup \{ s-2t \}$$ and $$X' \setminus( S\cup \{s-2t\})$$ form a partition of $$X'$$

• ($$\impliedby$$) Suppose that there is a partition $$P_1',P_2'$$ of $$X'$$ such that $$\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$$. Notice that this induces a natural partition $$P_1$$ and $$P_2$$ of $$X$$ such that WLOG we have that $$\begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*}$$ $$\begin{equation*} \implies s-2t+\sum_{x \in P_1}x+\sum_{x \in P_1}x= \sum_{x \in P_2}x+\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}$$

Hence from a solution $$t=\sum_{x \in S}x$$ we can form a parition $$P_1 =S\cup \{ s-2t \}$$, $$P_2=X' \setminus( S\cup \{s-2t\})$$ and conversely from a partition $$P_1',P_2'$$ we can form a soltuion $$t=\sum_{x \in P_1'\setminus \{s-2t\}}x$$ and therefore the mapping $$f:(X,t)\rightarrow X'$$ is a reduction (because $$(X,t)$$ is in the language/set SUBSETSUM $$\Leftrightarrow X'=f(X,t)$$ is in the language/set PARTITION) and it is clear to see that the transformation was done in polynomial time.

Subset Sum:

Input: {a1,a2,...,am} s.t M={1..m} and ai are non negative integer and S⊆{1..k} and Σai(i∈S) = t

Partition:

Input: {a1,a2,...,am} and S⊆ {1,· · ·,m} s.t Σai(i∈S) = Σaj(j∉S)

Partition Np Proof: if prover provides a partitions(P1,P2) for verifier, verifier can easily calculate the sum of P1 and P2 and check if the result is 0 in linear time.

NP_Hard: SubsetSum ≤p PARTITION

Let x be input of SubsetSum and x=〈a1,a2,...,am,t〉 and Σai(i from 1 to m) = a

Case1: 2t >= a:

Let f(x)=〈a1,a2,...,am,am+1〉 where am+1= 2t−a

We want to show that x∈SubsetSum ⇔ f(x)∈PARTITION

so there exist S⊆ {1,...,m} s.t T = {1..m} - S and Σai(i∈T) = a-t

and Let T' = {1...m,m+1} - S so Σaj(j∈T') = a-t+2t-a = t

which is exactly Σai(i∈S)= t and it shows f(x)∈PARTITION

now We also will show that f(x)∈PARTITION ⇔ x∈SubsetSum

so there exist S⊆ {1,...,m,m+1} s.t T = {1,...,m,m+1} - S and Σai (i∈T)= [a+(2t-a)-t]=t

and it shows Σai(i∈T) = Σaj(j∈S) so m+1∈T and S⊆ {1,· · ·,m} and Σai(i∈S)= t

so x∈SubsetSum

Case 2: 2t =< a :

we can check same but just this time am+1 is a−2t

this link has a good description of both reductions, partition to subset-sum and subset-sum to partition. I think it is more obvious than YUVAL's answer. useful link