-1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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/

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – user918212
    Jun 3 at 22:10
  • $\begingroup$ 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$. $\endgroup$ Jun 4 at 8:26
  • $\begingroup$ 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. $\endgroup$
    – user918212
    Jun 5 at 2:49
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 5 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.