7
$\begingroup$

Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete.

Hint: Use the exact cover problem.

The exact cover problem is the following: Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a set cover consisting of a subfamily of pairwise disjoint sets?

First of all, to show that this problem is in $\mathcal{NP}$ do we have to do the following?

A nondeterministic Turing machine can first guess which the subsequence of that we are looking for is and then verify that it sums to exactly k in linear time. Is this correct?

To show that it is NP-complete how could we reduce the exact cover problem to subset sum? Is it as follows?

The exact cover problem has a solution iff every element is in exactly one set.

We consider the set $S$ and the number $k$ such that each number corresponds to a set of elements and $k$ corresponds to the whole set. Suppose there are $n$ elements and $k$ different sets.

We replace each set S with a number that is $1$ in its ith position if i is in S and has a $0$ in its ith position otherwise.

We set k to a number that is $n$ copies of the number $1$.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Try proving that your reduction works. If you succeed, you will know that it does. Otherwise, back to the drawing board. $\endgroup$
    – Yuval Filmus
    Dec 18, 2014 at 3:10

2 Answers 2

Reset to default
6
$\begingroup$

Basic idea: In the exact cover problem, each element is reduced to a number. Then, each set is reduced to the sum of the numbers it covers. Finally, set $k$ to be the sum of all numbers.

This reduction always works one way: If a solution exists for the exact cover problem, a solution also exists for the subset sum problem.

The hard part is to prove the other way. Trivial numbers don't work. Suppose the elements are reduced to $1,2,3,4$, and the sets are

  • $S_1=\{3,4\}$
  • $S_2=\{3\}$

The reduction to subset sum is the numbers $7,3$ and $k=10$, which return YES but there's no solution to the exact cover problem!

We need to be smarter in choosing the numbers. Noticed the flaw in the previous numbers is that $3$ can replace $1,2$. We don't want any number to be replaced. Hence, we want the numbers to have sufficiently large gaps. Suppose in an exact cover problem of $n$ elements, the first element is reduced to $1$. How large should the second number be? There are $2^{n-1}$ sets that can include the first number. So, the second element should be reduced to a number larger than $2^{n-1}$ such that no matter how many times $1$ appears, it cannot replace the second number. Let's just reduce the second element to $2^n$. The same argument applies to the third argument, so we reduce it to $2^n\times 2^n=4^n$.

In conclusion, the $i$-th element in the exact cover problem has a value of $2^{in}$. Each set is reduced to the sum of numbers it covers.

Now we showed that exact cover is in NP-Hard. We need to prove that it is also in NP in order to show that it is NP-Complete. I think that's relatively simple. If you need help for that, I'll provide some hints for you.

Improve this answer
$\endgroup$
3
$\begingroup$

Subset Sum can be easily transformed from Partition problem. The proof of reducing Exact Cover to it is similar to the one from 3-Dimensional Matching, and you can find it in the textbook by Garey and Johnson. The proof is somewhat complicated.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.