# 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?

• 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

Define your $$\rm P{\small ARTITION}(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 $$\rm P {\small ARTITION}(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 $$\rm S{\small UBSET}(S,k)$$ problem to the problem asking for existence of two partitions of $$S$$ with equal sums of elements---$$\rm P{\small ARTITION}(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!) $$\rm P{\small ARTITION}(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.