MHB The knapsack problem is NP-complete

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion centers on demonstrating that the knapsack problem is NP-complete by reducing the exact cover problem to it. Participants explore the necessary steps for this reduction, including constructing integers from subsets of the exact cover and establishing a relationship between the two problems. Key points include the representation of subsets as binary numbers in base λ+1, which ensures no carries occur during addition, and how this leads to a solution in the knapsack problem if and only if there is a solution in the exact cover problem. The conversation emphasizes understanding polynomial time reductions and the implications of these transformations in proving NP-completeness.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Show that the knapsack 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 follwing:
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?

So, do I have to reduce the exact cover problem to the knapsack problem??

Could you give me some hints how I could do that?? (Wondering)
 
Technology news on Phys.org
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 the knapsack problem??

Could you give me some hints??
 
For the reduction do we have to map the sets $S_j$ into the integers $i_j$ ?? (Wondering)
 
I searched in Google and I found the following reduction:

Let $A=\{a_1, a_2, \dots , a_m\}$ and $A_1 , A_2, \dots, A_{\lambda}$ be an arbitrary instance of Exact Cover.

An instance of Knapsack can be obtained in polynomial time as follows.

$S=\{u_1, u_2, \dots , u_{\lambda}\}$ and $k=\sum_{i=0}^{m-1}(\lambda+1)^i$, where for $1 \leq j \leq \lambda$, $u_j=\sum_{i=1}^{m}e_{j,i}(\lambda+1)^{i-1}$
with $e_{j,i}=1$ if $a_{i} \in A_i$ and $e_{j,i}=0$ if $a_{i} \notin A_i$.

So, the Knapsack problem has a solution iff the Exact Cover problem has a solution.I haven't understood why using this reduction we conclude that the Knapsack problem has a solution iff the Exact Cover problem has a solution. Could you explain it to me?? (Wondering)
 
mathmari said:
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.
Yes.

mathmari said:
I searched in Google and I found the following reduction:

Let $A=\{a_1, a_2, \dots , a_m\}$ and $A_1 , A_2, \dots, A_{\lambda}$ be an arbitrary instance of Exact Cover.

An instance of Knapsack can be obtained in polynomial time as follows.

$S=\{u_1, u_2, \dots , u_{\lambda}\}$ and $k=\sum_{i=0}^{m-1}(\lambda+1)^i$, where for $1 \leq j \leq \lambda$, $u_j=\sum_{i=1}^{m}e_{j,i}(\lambda+1)^{i-1}$
with $e_{j,i}=1$ if $a_{i} \in A_i$ and $e_{j,i}=0$ if $a_{i} \notin A_i$.

So, the Knapsack problem has a solution iff the Exact Cover problem has a solution.I haven't understood why using this reduction we conclude that the Knapsack problem has a solution iff the Exact Cover problem has a solution.
This is described in Lewis & Papadimitriou (2nd edition), Theorem 7.3.5. Basically, each of the $\lambda$ subsets $A_j$ is represented as an $m$-digit number $e_{j1}\dots e_{jm}$ to the base $\lambda+1$. Here $e_{ji}=1$ if $a_i\in A_j$ and $e_{ji}=0$ otherwise. Thus, $e_{j1}\dots e_{jm}$ is the characteristic function (or sequence) of subset $A_j$. Since numbers are to the base $\lambda+1$ and there are only $\lambda$ numbers, adding them does not produce a carry. And adding numbers corresponding to an exact cover produces exactly $\underbrace{11\dots1}_m$.
 
Evgeny.Makarov said:
This is described in Lewis & Papadimitriou (2nd edition), Theorem 7.3.5. Basically, each of the $\lambda$ subsets $A_j$ is represented as an $m$-digit number $e_{j1}\dots e_{jm}$ to the base $\lambda+1$. Here $e_{ji}=1$ if $a_i\in A_j$ and $e_{ji}=0$ otherwise. Thus, $e_{j1}\dots e_{jm}$ is the characteristic function (or sequence) of subset $A_j$. Since numbers are to the base $\lambda+1$ and there are only $\lambda$ numbers, adding them does not produce a carry. And adding numbers corresponding to an exact cover produces exactly $\underbrace{11\dots1}_m$.

If we have for example $A=\{7, 5, 19, 1, 12, 8, 14\}$ and $A_1=\{7, 19, 12, 14\}, A_2=\{7, 5, 8\}, A_3=\{5, 1, 8\}, A_4=\{19, 1, 8, 4\}$

$m=7, \lambda=4$

For $j=1$ we have $e_{11}=1100000, e_{12}=0110000, e_{13}=1001000, e_{14}=0011000, e_{15}=1000000, e_{16}=0111000, \\ e_{17}=1000000$

right ?? (Wondering)

So, $u_1=\sum_{i=1}^{7}e_{1i}5^{i-1}=1100000 +0110000 \cdot 5+1001000 \cdot 5^2+0011000\cdot 5^3+1000000 \cdot 5^4+0111000 \cdot 5^5+1000000 \cdot 5^6$

Is this correct?? (Wondering)

Or have I understood it wrong?? (Wondering)

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?

The Set cover is the following:
Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a subfamily of $r$ sets $S_{i_1}, S_{i_2}, \dots , S_{i_r}$ such that $\cup_{j=1}^r S_{i_j}=\cup_{j=1}^n S_j$ ? Does this mean that at the Knapsack problem we have to find a subsequence of $r$ terms??
 
Last edited by a moderator:
Evgeny.Makarov said:
Basically, each of the $\lambda$ subsets $A_j$ is represented as an $m$-digit number $e_{j1}\dots e_{jm}$ to the base $\lambda+1$.

Why do we take the numbers in base $\lambda+1$ ?? (Wondering)
Evgeny.Makarov said:
Since numbers are to the base $\lambda+1$ and there are only $\lambda$ numbers, adding them does not produce a carry.

Could you explain it to me?? (Wondering)
Evgeny.Makarov said:
And adding numbers corresponding to an exact cover produces exactly $\underbrace{11\dots1}_m$.

So, if the result is $\underbrace{11\dots1}_m$, both the exact cover and the knapsack problem have a solution ?? (Wondering)
 
mathmari said:
If we have for example $A=\{7, 5, 19, 1, 12, 8, 14\}$ and $A_1=\{7, 19, 12, 14\}, A_2=\{7, 5, 8\}, A_3=\{5, 1, 8\}, A_4=\{19, 1, 8, 4\}$

$m=7, \lambda=4$
Yes. Working with these sets would be much easier if numbers were sorted. Note that constructing the knapsack problem instance requires fixing an order on elements of $A$, and standard order would make things easier.

mathmari said:
For $j=1$ we have $e_{11}=1100000, e_{12}=0110000, e_{13}=1001000, e_{14}=0011000, e_{15}=1000000, e_{16}=0111000, \\ e_{17}=1000000$
No. Each $e_{ji}$ is either 0 or 1. Please reread my post.

mathmari said:
Does this mean that at the Knapsack problem we have to find a subsequence of $r$ terms??
I am not sure what you mean by a term here.

mathmari said:
Why do we take the numbers in base $\lambda+1$ ?
Because
Evgeny.Makarov said:
Since numbers are to the base $\lambda+1$ and there are only $\lambda$ numbers, adding them does not produce a carry.

mathmari said:
Could you explain it to me?
Try adding at most 9 decimal numbers whose digits are 0 or 1 and see if you get a carry.

mathmari said:
So, if the result is $\underbrace{11\dots1}_m$, both the exact cover and the knapsack problem have a solution ?
The given instance of Exact Cover and the constructed instance of Knapsack, yes. Moreover, if a subset of numbers summing to 11...1 does not exist, then both instances do not have a solution. The idea of polynomial reduction is that the given instance has a solution iff the constructed instance does.
 
If we have for example $A=\{1, 5, 7, 8, 12, 14, 19\}$ and $A_1=\{7, 12, 14, 19\}, A_2=\{5, 7, 8\}, A_3=\{1, 5, 8\}, A_4=\{1, 4, 8, 19\}$

$m=7, \lambda=4$

For $j=1$ we have $e_{11}=0, e_{12}=0, e_{13}=1, e_{14}=0, e_{15}=1, e_{16}=1, e_{17}=1$

We map each set $A_j$ into a $m-$digit integer $e_{j1} \dots e_{jm}$, does this mean that $u_1=0010111$ ?? (Wondering)

This is equal to $u_1=\sum_{i=1}^{7}e_{1i}5^{i-1}=5^2+5^4+5^5+5^6$ in base $5$, right?? (Wondering)
mathmari said:
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?

The Set cover is the following:
Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a subfamily of $r$ sets $S_{i_1}, S_{i_2}, \dots , S_{i_r}$ such that $\cup_{j=1}^r S_{i_j}=\cup_{j=1}^n S_j$ ? Does this mean that at the Knapsack problem we have to find a subsequence of $r$ terms??

Evgeny.Makarov said:
I am not sure what you mean by a term here.

Do we have the index $\lambda$ from the set cover problem?? (Wondering)
At the definition above do we have taken $r=\lambda$ ?? (Wondering)
Evgeny.Makarov said:
Try adding at most 9 decimal numbers whose digits are 0 or 1 and see if you get a carry.

What do you mean with "get a carry" ?? (Wondering)
Evgeny.Makarov said:
The idea of polynomial reduction is that the given instance has a solution iff the constructed instance does.

Why do we reduce the Exact Cover problem to the Knapsack problem in polynomial time?? (Wondering)
 
  • #10
mathmari said:
If we have for example $A=\{1, 5, 7, 8, 12, 14, 19\}$ and $A_1=\{7, 12, 14, 19\}, A_2=\{5, 7, 8\}, A_3=\{1, 5, 8\}, A_4=\{1, 4, 8, 19\}$

$m=7, \lambda=4$

For $j=1$ we have $e_{11}=0, e_{12}=0, e_{13}=1, e_{14}=0, e_{15}=1, e_{16}=1, e_{17}=1$

We map each set $A_j$ into a $m-$digit integer $e_{j1} \dots e_{jm}$, does this mean that $u_1=0010111$ ?
Good, now it's correct.

mathmari said:
This is equal to $u_1=\sum_{i=1}^{7}e_{1i}5^{i-1}=5^2+5^4+5^5+5^6$ in base $5$, right?
Yes.

mathmari said:
What do you mean with "get a carry" ?
See Wikipedia.
 
  • #11
Evgeny.Makarov said:
Try adding at most 9 decimal numbers whose digits are 0 or 1 and see if you get a carry.

We don't get a carry, do we?? (Wondering)
Evgeny.Makarov said:
The idea of polynomial reduction is that the given instance has a solution iff the constructed instance does.

Why do we reduce the Exact Cover problem to the Knapsack problem in polynomial time?? (Wondering)
 
  • #12
mathmari said:
We don't get a carry, do we?
You tell me.

mathmari said:
Why do we reduce the Exact Cover problem to the Knapsack problem in polynomial time?
Try to come up with a more specific question or read the textbook. Do you have a reason to believe that it is not polytime?
 
  • #13
Evgeny.Makarov said:
You tell me.

We don't get. We would get if we would add more than $9$ decimal numbers, right?? (Wondering)
Evgeny.Makarov said:
Try to come up with a more specific question or read the textbook. Do you have a reason to believe that it is not polytime?

It is polytime because p(n) steps are needed to "translate" any input of the Exact Cover problem into an input of the Knapsack problem, where p(n) is any polynomial, right?? (Wondering)

Do we have to justify why it is polytime when we mention that?? (Wondering)
 
  • #14
mathmari said:
We don't get. We would get if we would add more than $9$ decimal numbers, right?
We might get a carry if we added more than 9 decimal numbers. But the fact that adding $\le 9$ numbers does not produce a carry uses the fact that the numbers have only 0 or 1 as digits.

mathmari said:
It is polytime because p(n) steps are needed to "translate" any input of the Exact Cover problem into an input of the Knapsack problem, where p(n) is any polynomial, right?
"Where $p(n)$ is some polynomial".

mathmari said:
Do we have to justify why it is polytime when we mention that?
Yes.
 
  • #15
So, can I formulate the reduction as followed?? (Wondering)

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?

The Set cover is the following:
Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a subfamily of $\lambda$ sets $S_{i_1}, S_{i_2}, \dots , S_{i_{\lambda}}$ such that $\cup_{j=1}^{\lambda} S_{i_j}=\cup_{j=1}^n S_j$ ?
We will reduce the Exact Cover problem to the Knapsack problem.

Let the set $A=\{a_1, a_2, \dots , a_m\}$ and the subsets $A_1, A_2, \dots , A_{\lambda}$, an instance of the Exact Cover problem.

We will construct an instance of the Knapsack problem in polynomial time.
That means that we will construct the integers $i_1, i_2 \dots , i_n$ and the integer $k$ such that there is a subset $P \subseteq \{1, \dots , n\}$ with $\sum_{j \in P} i_j=k$ iff there is a family of $\lambda$ pairwise disjoint sets that covers the whole $A$.

Each of the $\lambda$ subsets $A_j$ corresponds to an integer with $\lambda$ digits, $e_{j1} \dots e_{j \lambda}$ in the base $\lambda+1$, where $e_{ji}=1$ if $a_i \in A_j$ and $e_{ji}=0$ otherwise.

So, we have $\lambda$ integers $i_1, \dots , i_{\lambda}$ where $i_j=\sum_{r=1}^{\lambda}e_{jr}(\lambda+1)^{i-1}$.

We set $k=\sum_{r=0}^{\lambda-1}(\lambda+1)^r$.

So, the question is whether there is a subset the terms of which sum to exactly $k$, that means to $\underbrace{111 \dots 1}_{\lambda}$.

Therefore, this instance of the Knapsack problem has a solution iff the initial instance of the Exact Cover problem has a solution.

The reduction is polytime because p(n) steps are needed to "translate" any input of the Exact Cover problem into an input of the Knapsack problem, where p(n) is some polynomialIs it correct?? (Wondering)

Could I improve something?? (Wondering)

Are the indices that I used correct?? (Wondering)
 
Last edited by a moderator:

Similar threads

Replies
6
Views
2K
Replies
1
Views
3K
Replies
17
Views
4K
Replies
6
Views
2K
Replies
2
Views
4K
Back
Top