1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 6 '17 at 6:43
  • $\begingroup$ @YuvalFilmus If i opened this question is because i couldn't solve the exercise. I would appreciate any help. $\endgroup$ – jscherman Aug 6 '17 at 7:00
2
$\begingroup$

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)$.

The reduction to the latter can be done as following:
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.

$\endgroup$

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.