<p><strong>tl;dr</strong>: Showing that the Extended Knapsack problem is NP-Complete is easy through the original Knapsack, but you have to define the two problems correctly.</p>
<p>For a problem to be NP-Complete, it has to be stated as a <strong>decision problem</strong>. This means that its output is a binary variable (YES / NO). The decision version of the 0-1 Knapsack problem (which is indeed NP-Complete), is similar to the problem you described with an additional parameter <span class="math-container">$N$</span> (a threshold for the value). An algorithm has to output YES iff there exist <span class="math-container">$x_i \in \{0, 1\}$</span> such that</p>
<p><span class="math-container">$$\sum_{i=1}^nv_i x_i \geq N\quad\text{and}\quad\sum_{i=1}^n w_ix_i &lt; M$$</span></p>
<p>To solve your version of the 0-1 Knapsack problem (usually referred to as the <em>optimization</em> variant) it suffices to perform a binary search on the optimal value of <span class="math-container">$N$</span>. This will require a logarithmic number of calls to a solver of the decision variant.</p>
<p><strong>Decision Variant of the Extended Knapsack Problem</strong>. To show that the Extended Knapsack problem is NP-Complete, we have to write it as a decision problem. It is not clear from the question what is the exact quantity we are optimizing over (do we want to maximize the <em>sum</em> of the values of each instance?). Still, a reasonable decision variant could be to have a value threshold <span class="math-container">$N^i$</span> and a weight threshold <span class="math-container">$M^i$</span> for each instance. Then our algorithm should output YES iff there exists a solution <span class="math-container">$\{a_1, \dots, a_m\}$</span> such that
<span class="math-container">$$\sum_{i=1}^nv_i^j x_i \geq N^j\quad\text{and}\quad\sum_{i=1}^n w_i^jx_i &lt; M^j \quad\forall j\in \{1, \dots, \ell\}$$</span></p>
<p>where <span class="math-container">$x_i = 1$</span> if and only if item <span class="math-container">$i$</span> is in the solution <span class="math-container">$\{a_1, \dots, a_m\}$</span> and <span class="math-container">$x_i = 0$</span> otherwise.</p>
<p><strong>NP-Completeness</strong>. Now to show that a problem <span class="math-container">$L$</span> is NP-Complete, we have to show two things.</p>
<ol>
<li><span class="math-container">$L \in NP$</span>. This means that there exists a short certificate and a polynomial-time algorithm which outputs YES when given a correct certificate and NO otherwise. The certificate for the Extended Knapsack is very similar to the certificate of the original Knapsack problem.</li>
<li><span class="math-container">$L$</span> is <span class="math-container">$NP$</span>-Hard. This is done by reducing from a problem known to be NP-Hard (or NP-Complete) to <span class="math-container">$L$</span>. Since the original Knapsack problem is a special case (<span class="math-container">$\ell = 1$</span>) of the Extended Knapsack problem, constructing such a reduction from Knapsack to Extended Knapsack is easy.</li>
</ol>
<p><strong>References</strong>. <a href="https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/mit6_046js15_lec16/" rel="nofollow noreferrer">https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/mit6_046js15_lec16/</a></p>

CC BY-SA 4.0
2022-06-03T22:10:17.400Z
Thank you for the clear and helpful answer.  in (2.) you say that "constructing such a reduction from Knapsack" is easy.  Can you elaborate on why (I am very new to this area)?  Does it just follow from the fact that given an algorithm to solve the extended knapsack problem, you can use it to solve the original knapsack problem?
user918212
CC BY-SA 4.0
2022-06-04T08:26:33.817Z
Precisely. A reduction from problem A to problem B is a way to show that an efficient algorithm that solves B can also be used to solve problem A. This intuitively means that B is "at least as hard" as A, so it is NP-Hard.

Here we reduce from Knapsack to Extended Knapsack. Having an algorithm for Extended Knapsack allows us to solve Knapsack with parameters $(V, W, N, M)$ by setting $\ell = 1$ and $V^1 = V, W^1 = W, N^1 = N, M^1 = M$.
Angelos Pelecanos
CC BY-SA 4.0
2022-06-05T02:49:09.547Z
I see, but the subtlety that has me confused is that an algorithm that solves the extended problem seems to be different than one that solves the original problem, because the extended problem involves more than one instance, so given an instance of the original problem, to solve it with the algorithm you would need at least one other instance with the same solution before you could apply the algorithm solving the extended problem.
user918212
CC BY-SA 4.0
2022-06-05T07:56:41.100Z
I don't think the definition of the Extended Knapsack problem states that the number of instances has to be more than $1$ (it only mentions $\ell \in \mathbb{N}$). But even if it requires $\ell > 1$, you could set $V^1 = V^2 = V$, $W^1 = W^2 = W$, $N^1 = N^2 = N$ and $M^1 = M^2 = M$. That way, you have two identical instances of the original Knapsack problem.
Angelos Pelecanos
CC BY-SA 4.0
2022-06-03T20:33:35.683Z
2022-06-03T20:33:35.683Z
Angelos Pelecanos
<p>In this question I give a modified version of the knapsack problem, which I call the &quot;extended knapsack problem&quot;.  I want to show that this &quot;extended&quot; problem is NP-Complete, but I am unclear if showing this is trivial by its correspondence to the knapsack problem or requires its own separate reduction to some NP-Complete problem.</p>
<p><strong>0-1 Knapsack problem definition:</strong> let <span class="math-container">$V = \{v_1, v_2, ..., v_n\}$</span> be a set of values, and <span class="math-container">$W = \{w_1, w_2, ..., w_n\}$</span> be the corresponding set of weights, so that item <span class="math-container">$x_i \in \{0, 1\}$</span> has value <span class="math-container">$v_i$</span> and weight <span class="math-container">$w_i$</span>.  Let <span class="math-container">$M$</span> denote the maximum weight.  Then the 0-1 knapsack problem asks us to maximize <span class="math-container">$\sum_{i=1}^n v_ix_i$</span> subject to the constraint <span class="math-container">$\sum_{i=1}^n w_ix_i &lt; M$</span> where <span class="math-container">$x_i \in \{0, 1\}$</span>.</p>
<p>I am going to use the following convention for writing solutions to the 0-1 knapsack problem (which becomes useful later): assume the sets <span class="math-container">$V$</span> and <span class="math-container">$W$</span> <em>are ordered</em>.  Then instead of referring to a solution to the 0-1 knapsack problem by the items <span class="math-container">$x_{a_1}, x_{a_2}, ..., x_{a_m}$</span> which have value 1 and are solutions, we can instead write a solution as a set of <span class="math-container">$m$</span> indices, which determine the items <span class="math-container">$x_i$</span>.  Then a solution of form <span class="math-container">$\{a_1, a_2, ..., a_m\}$</span> where <span class="math-container">$a_i \in \mathbb{N}$</span> and <span class="math-container">$m \leq n$</span> reads as &quot;in the sums to be optimized, if <span class="math-container">$i = a_j$</span>, then <span class="math-container">$x_i = 1$</span>.&quot;</p>
<p><strong>Extended knapsack problem.</strong> Take <span class="math-container">$l \in \mathbb{N}$</span> instances of the 0-1 knapsack problem, so we have <span class="math-container">$l$</span> pairs <span class="math-container">$(V^1, W^1), (V^2, W^2),...,(V^l, W^l)$</span>, where <span class="math-container">$|V^i|=|W^i|=n$</span> for all <span class="math-container">$i$</span> and <span class="math-container">$n$</span> is fixed.  Finally, we take each of these instances to have the <em>same solution</em> (using the index convention given above).  So that if instance <span class="math-container">$(V^1, W^1)$</span> has solution <span class="math-container">$\{a_1, a_2,..., a_m\}$</span>, then <em>every other instance</em> has the solution <span class="math-container">$\{a_1, a_2,...,a_m\}$</span> (again this is a set of indices over the items <span class="math-container">$\{x_1, x_2,...,x_n\}$</span> where we take each <span class="math-container">$x_i$</span> to have some fixed position in the set so this indexing makes sense).</p>
<p><strong>Question:</strong> How do you show the extended knapsack problem is NP-Complete?  One part of me thinks showing this is trivial, since being able to solve the extended knapsack problem implies you can solve the original knapsack problem, and vice versa, so there is this &quot;equivalence&quot; between them.  But, on the other hand, the extended knapsack problem seems to &quot;reveal more information&quot;, and hence I would think that it could be easier to solve than the original knapsack problem, and hence would require its own reduction proof to establish the fact that it is NP-Complete.  How should I be thinking about this?</p>

<cc.complexity-theory><complexity-classes><reductions>
Showing that a modification of an NP-Complete problem is also NP-Complete
user918212
# Showing that a modification of an NP-Complete problem is also NP-Complete

(Asked by: username_0 on 2022-06-03)

In this question I give a modified version of the knapsack problem, which I call the "extended knapsack problem". I want to show that this "extended" problem is NP-Complete, but I am unclear if showing this is trivial by its correspondence to the knapsack problem or requires its own separate reduction to some NP-Complete problem.

**0-1 Knapsack problem definition:** let $V = \{v\_1, v\_2, ..., v\_n\}$ be a set of values, and $W = \{w\_1, w\_2, ..., w\_n\}$ be the corresponding set of weights, so that item $x\_i \in \{0, 1\}$ has value $v\_i$ and weight $w\_i$. Let $M$ denote the maximum weight. Then the 0-1 knapsack problem asks us to maximize $\sum\_{i=1}^n v\_ix\_i$ subject to the constraint $\sum\_{i=1}^n w\_ix\_i < M$ where $x\_i \in \{0, 1\}$.

I am going to use the following convention for writing solutions to the 0-1 knapsack problem (which becomes useful later): assume the sets $V$ and $W$ *are ordered*. Then instead of referring to a solution to the 0-1 knapsack problem by the items $x\_{a\_1}, x\_{a\_2}, ..., x\_{a\_m}$ which have value 1 and are solutions, we can instead write a solution as a set of $m$ indices, which determine the items $x\_i$. Then a solution of form $\{a\_1, a\_2, ..., a\_m\}$ where $a\_i \in \mathbb{N}$ and $m \leq n$ reads as "in the sums to be optimized, if $i = a\_j$, then $x\_i = 1$."

**Extended knapsack problem.** Take $l \in \mathbb{N}$ instances of the 0-1 knapsack problem, so we have $l$ pairs $(V^1, W^1), (V^2, W^2),...,(V^l, W^l)$, where $|V^i|=|W^i|=n$ for all $i$ and $n$ is fixed. Finally, we take each of these instances to have the *same solution* (using the index convention given above). So that if instance $(V^1, W^1)$ has solution $\{a\_1, a\_2,..., a\_m\}$, then *every other instance* has the solution $\{a\_1, a\_2,...,a\_m\}$ (again this is a set of indices over the items $\{x\_1, x\_2,...,x\_n\}$ where we take each $x\_i$ to have some fixed position in the set so this indexing makes sense).

**Question:** How do you show the extended knapsack problem is NP-Complete? One part of me thinks showing this is trivial, since being able to solve the extended knapsack problem implies you can solve the original knapsack problem, and vice versa, so there is this "equivalence" between them. But, on the other hand, the extended knapsack problem seems to "reveal more information", and hence I would think that it could be easier to solve than the original knapsack problem, and hence would require its own reduction proof to establish the fact that it is NP-Complete. How should I be thinking about this?

**Tags:** cc.complexity-theory, complexity-classes, reductions

---

## 1 answers

### Answer by username_1 on 2022-06-03. Score: 1 | Accepted answer

**tl;dr**: Showing that the Extended Knapsack problem is NP-Complete is easy through the original Knapsack, but you have to define the two problems correctly.

For a problem to be NP-Complete, it has to be stated as a **decision problem**. This means that its output is a binary variable (YES / NO). The decision version of the 0-1 Knapsack problem (which is indeed NP-Complete), is similar to the problem you described with an additional parameter $N$ (a threshold for the value). An algorithm has to output YES iff there exist $x\_i \in \{0, 1\}$ such that

$$\sum\_{i=1}^nv\_i x\_i \geq N\quad\text{and}\quad\sum\_{i=1}^n w\_ix\_i < M$$

To solve your version of the 0-1 Knapsack problem (usually referred to as the *optimization* variant) it suffices to perform a binary search on the optimal value of $N$. This will require a logarithmic number of calls to a solver of the decision variant.

**Decision Variant of the Extended Knapsack Problem**. To show that the Extended Knapsack problem is NP-Complete, we have to write it as a decision problem. It is not clear from the question what is the exact quantity we are optimizing over (do we want to maximize the *sum* of the values of each instance?). Still, a reasonable decision variant could be to have a value threshold $N^i$ and a weight threshold $M^i$ for each instance. Then our algorithm should output YES iff there exists a solution $\{a\_1, \dots, a\_m\}$ such that
$$\sum\_{i=1}^nv\_i^j x\_i \geq N^j\quad\text{and}\quad\sum\_{i=1}^n w\_i^jx\_i < M^j \quad\forall j\in \{1, \dots, \ell\}$$

where $x\_i = 1$ if and only if item $i$ is in the solution $\{a\_1, \dots, a\_m\}$ and $x\_i = 0$ otherwise.

**NP-Completeness**. Now to show that a problem $L$ is NP-Complete, we have to show two things.

1. $L \in NP$. This means that there exists a short certificate and a polynomial-time algorithm which outputs YES when given a correct certificate and NO otherwise. The certificate for the Extended Knapsack is very similar to the certificate of the original Knapsack problem.
2. $L$ is $NP$-Hard. This is done by reducing from a problem known to be NP-Hard (or NP-Complete) to $L$. Since the original Knapsack problem is a special case ($\ell = 1$) of the Extended Knapsack problem, constructing such a reduction from Knapsack to Extended Knapsack is easy.

**References**. <https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/mit6_046js15_lec16/>

> **Comments:**
> **username_0**: Thank you for the clear and helpful answer.  in (2.) you say that "constructing such a reduction from Knapsack" is easy.  Can you elaborate on why (I am very new to this area)?  Does it just follow from the fact that given an algorithm to solve the extended knapsack problem, you can use it to solve the original knapsack problem?  
> **username_1**: Precisely. A reduction from problem A to problem B is a way to show that an efficient algorithm that solves B can also be used to solve problem A. This intuitively means that B is "at least as hard" as A, so it is NP-Hard.  Here we reduce from Knapsack to Extended Knapsack. Having an algorithm for Extended Knapsack allows us to solve Knapsack with parameters $(V, W, N, M)$ by setting $\ell = 1$ and $V^1 = V, W^1 = W, N^1 = N, M^1 = M$.  
> **username_0**: I see, but the subtlety that has me confused is that an algorithm that solves the extended problem seems to be different than one that solves the original problem, because the extended problem involves more than one instance, so given an instance of the original problem, to solve it with the algorithm you would need at least one other instance with the same solution before you could apply the algorithm solving the extended problem.  
> **username_1**: I don't think the definition of the Extended Knapsack problem states that the number of instances has to be more than $1$ (it only mentions $\ell \in \mathbb{N}$). But even if it requires $\ell > 1$, you could set $V^1 = V^2 = V$, $W^1 = W^2 = W$, $N^1 = N^2 = N$ and $M^1 = M^2 = M$. That way, you have two identical instances of the original Knapsack problem.  

---

