# Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete.

The Partition problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ can be partitionated in two subsets such that the difference between the sums of the both sets are lesser or equal to $K$.

Prove that the partition problem is NP-Complete using that SubsetSum so is it.

Any ideas?

• Your title asks to prove the SubsetSum problem is NP-complete, while body text asks to prove the Partition problem is NPC. – fade2black Aug 6 '17 at 6:10
• This is a standard exercise, and it is really best that you solve it on your own. We will not be available to help you on your exam. – Yuval Filmus Aug 6 '17 at 6:43
• @YuvalFilmus If i opened this question is because i couldn't solve the exercise. I would appreciate any help. – jscherman Aug 6 '17 at 7:00
• @fade2black yep, my bad. I've already changed it =) – jscherman Aug 6 '17 at 7:01

Define your $PARTITION(S, K)$ problem as:
"Are there partitions $S_1, S_2$ of $S$ such that $|\text{sum}(S_1) - \text{sum}(S_2)| \leq K$, where $\text{sum}(S_i)$ is the sum of all elements of $S_i$?".
Then $PARTITION(S, 0)$ would mean $|\text{sum}(S_1) - \text{sum}(S_2)| \leq 0$ which is true only if $\text{sum}(S_1) = \text{sum}(S_2)$. Thus, given $S$ we could reduce the $SUBSET(S,k)$ problem to the problem asking for existence of two partitions of $S$ with equal sums of elements - $PARTITION(S, 0)$.
Let $s=\text{sum(S)}$ and define a new set $S_{new} = S \cup \{2k − s\}$. We choose $2k-s$ since the sum of $S_{new}$ is $2k-s+s = 2k = k+k$, and we want two partitions with equal sizes equal to $k$.
Now call (reduction!) $PARTITION(S_{new},0)$. If it returns YES/TRUE then $S_{new}$ can be partitioned into two sets $S_1$ and $S_2$ with sums equal to $k$. Also notice that either $S_1$ or $S_2$ can contain the new element $2k − s$ (since they are partitions) meaning that either $S_1$ or $S_2$ is a subset of $S$. Thus we have a subset (without the element $2k − s$) of $S$ with the sum $k$, and we return YES/TRUE. Otherwise, if we get NO/FALSE then return NO/FALSE.