How can I reduce Subset Sum to Partition?

Question

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!

Answer 1

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$.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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