patternMinor
Reducing Exact Cover to Subset Sum
Viewed 0 times
exactreducingsumcoversubset
Problem
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$.
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$.
Solution
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
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.
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.
Context
StackExchange Computer Science Q#35456, answer score: 6
Revisions (0)
No revisions yet.