19
$\begingroup$

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!

$\endgroup$
18
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ But the standard subset-sum problem uses all integers, and partition problem uses just non-negative integers... $\endgroup$ – gukoff Apr 19 '13 at 17:40
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 19 '13 at 20:26
  • 1
    $\begingroup$ Yes, I know, and this reduction is very easy. Just noting that it isn't the subset sum in it's "default" form. :) $\endgroup$ – gukoff Apr 20 '13 at 3:11
  • $\begingroup$ Would it also work if $L^{'}$ is $L \bigcup \{B, S-B\}$? as $|\{B, S-B\}| = B$, like $|L| = B$ $\endgroup$ – Curious Feb 28 '14 at 17:42
  • 1
    $\begingroup$ @Issam It wouldn't, this the PARTITION instance would always have the solution $L,\{B,S-B\}$. $\endgroup$ – Yuval Filmus Feb 28 '14 at 21:48
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 15 '17 at 14:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Rohit Kumar Jena Apr 15 '17 at 15:31
  • 1
    $\begingroup$ "Just providing a more complete proof" and also wrongly claiming that an existing answer is incorrect. $\endgroup$ – David Richerby Apr 15 '17 at 16:33
  • 1
    $\begingroup$ It's incorrect in the sense that it does not work for negative integers. :) Peace :) $\endgroup$ – Rohit Kumar Jena Apr 15 '17 at 16:43
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-3
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ Please do not post link-only answers. If the content at the link changes or becomes unavailable, your answer will become useless. Please amend your answer so that it is useful, even if the link is unavailable (for instance, restating the content in your own words and providing the link as reference and source). $\endgroup$ – Tom van der Zanden Jan 16 '16 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.