Showing that a modification of an NP-Complete problem is also NP-Complete

Question

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?

Answer 1

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/