1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – dave Feb 8 '17 at 17:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Mano Plizzi Feb 9 '17 at 9:32
  • 1
    $\begingroup$ Yes. can you write an answer to your own question then? $\endgroup$ – dave Feb 9 '17 at 12:46
2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Solution officially translated. $\endgroup$ – Pedrpan Oct 6 '18 at 7:56

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.