# Karp reduction from PARTITION to SUBSET SUM

PARTITION: Given a set of positive integers $A=\{a_1,...,a_n\}$ does there exist a subset of $A$ with sum equal to the sum of it's complement?

SUBSET SUM: Given a set of positive integers $A=\{a_1,...,a_n\}$ and another positive integer $B$, does there exist a subset of $A$ such that it's sum is equal to $B$?

I was trying to prove that if PARTITION is NP-complete then SUBSET SUM is also NP-complete, by reducing PART to SSUM.

My solution was: let $A=\{a_1,...,a_n\}$ be a set of positive integers. Then if A when fed into PART gives the solution $I=\{k_1,...,k_m\}$ (where $k_i$ are the indices of the members of the solution subset), then we construct $A'=\{a_1,...a_n,S\}$ where $S$ is the sum of $\{a_{k_1},a_{k_2},...,a_{k_m}\}$. $A'$ is a solution to SSUM.

My problem with this is that this goes only one way, meaning that we can't show that given A' then A is a solution to PART. Is this a problem? and how could i modify the proof to cover it?

• Your reduction shouldn't be dependent on a solution to PART. on input A you should output a set of integers A' and an integer B s.t. $(A',B) \in SSUM \iff A \in PART$. what should A',B be then? – dave Feb 8 '17 at 17:05
• So, i think i know what the problem is. If i just redefine S to be the (equal to the old S) half of the sum of A, then (A,S) is a solution of SSUM iff A is a solution to PART. – Mano Plizzi Feb 9 '17 at 9:32
• Yes. can you write an answer to your own question then? – dave Feb 9 '17 at 12:46

Let's say we have a canditate set $A=\{a_1,...,a_n\}$ to feed as input to PARTITION. There is a transformation in polynomial time $f$, with $f(A)=(A,B)$, where $B=$${\sum_{i=1}^n a_i }\over 2$.
Then $A$ is a solution to $PART$ if and only if $(A,B)$ is a solution to $SSUM$.
So we have $PART \le_m^p SSUM$

Here is a straightforward proof:

It is easy to see that SUBSETSUM can be verified in polynomial time; given a set of integers $$S$$ and an integer $$t$$ just evaluate the sum $$\sum_{x \in S}x$$ and verify that the equality $$t=\sum_{x \in S}x$$ holds, which is obviously a polynomial time verification (because summation is a polynomial operation and we are only performing at most $$|S|$$ many summations).

The core of the proof is in reducing PARTITION to SUBSETSUM; to that end given set $$X$$ we form a new set $$X'=X \setminus \{s-2t\}$$ where $$s=\sum_{x \in X}x$$ and the number $$s-2t\in X$$ is found in the following fashion:

• Is $$s$$ is odd then there must be an odd number $$x \in X$$ (otherwise $$s$$ would not be odd) and any odd number $$x \in X$$ is of the desired form $$s-2t$$ (a linear search can find the desired element).
• Is $$s$$ is even then any even number will be of the form $$s-2t$$. If no even number exists then if we let $$2X=\{2x_1,...,2x_n\}$$ we then notice that the following equivalence $$(\exists P_1',P_2'\subset2X)(\sum_{x \in P_1 }x=\sum_{x \in P_2}x) \Longleftrightarrow (\exists P_1,P_2\subset X)(\sum_{x \in P_1 }x=\sum_{x \in P_2}x)$$ gives us that we can replace $$X$$ with $$2X$$ and then perform the reduction (this is true because $$\sum_{x \in P_i' }x=2\sum_{x \in P_i }x$$).

We then let $$f:X \mapsto (X',t)$$. 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 \mapsto (X',t)$$ is a reduction (because $$X$$ is in the language/set PARTITION $$\Leftrightarrow (X',t)=f(X)$$ is in the language/set SUBSETSUM) and it is clear to see that the transformation was done in polynomial time.

• Solution officially translated. – Pedrpan Oct 6 '18 at 7:56