Statement

Lemma

Knapsack-search is NP-complete.

Proof

Note we already have Knapsack-search is NP so we just need to show it is NP-hard. We do this be finding a many-one reduction of the subset-sum problem to it. We already have Subset-sum problem is NP-complete so this gives us the desired result.

Suppose we have an instance of the subset-sum problem given by for and .

Construct a Knapsack-search problem with items with with weight and value . Then set the limit and goal .

Note this transformation is as we just need to construct the objects. So it is Polynomial time.

Suppose the constructed Knapsack-search problem provides solution , then provide this as the solution to the subset-sum problem.

This takes as we don’t need to change the solution. Therefore it is polynomial time.

Suppose we have a solution to the constructed Knapsack-search problem. Then we know