Karp reduction from PARTITION to SUBSET SUM

Question

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?

Answer 1

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$

Answer 2

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.