# Reducing Exact Cover to Subset Sum

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

• Try proving that your reduction works. If you succeed, you will know that it does. Otherwise, back to the drawing board. – Yuval Filmus Dec 18 '14 at 3:10

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.

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.