The knapsack problem is NP-complete

[mathmari]

Hey!

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)

 

[mathmari]

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??

 

[mathmari]

For the reduction do we have to map the sets $S_j$ into the integers $i_j$ ?? (Wondering)

 

[mathmari]

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)

 

[Evgeny.Makarov]

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.

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

 

[mathmari]

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??

 

[mathmari]

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)

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)

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)

 

[Evgeny.Makarov]

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.

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.

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.

Why do we take the numbers in base $\lambda+1$ ?

Because

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?

Try adding at most 9 decimal numbers whose digits are 0 or 1 and see if you get a carry.

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.

 

[mathmari]

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)

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??

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)

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)

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)

 

[Evgeny.Makarov]

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.

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.

What do you mean with "get a carry" ?

See Wikipedia.

 

[mathmari]

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)

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)

 

[Evgeny.Makarov]

We don't get a carry, do we?

You tell me.

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?

 

[mathmari]

You tell me.

We don't get. We would get if we would add more than $9$ decimal numbers, right?? (Wondering)

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)

 

[Evgeny.Makarov]

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.

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

Do we have to justify why it is polytime when we mention that?

Yes.

 

[mathmari]

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)