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$
  • $\begingroup$ Your title asks to prove the SubsetSum problem is NP-complete, while body text asks to prove the Partition problem is NPC. $\endgroup$ – fade2black Aug 6 '17 at 6:10
  • 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
  • $\begingroup$ @fade2black yep, my bad. I've already changed it =) $\endgroup$ – jscherman Aug 6 '17 at 7:01
2
$\begingroup$

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

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

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