PDF of Eric’s handwritten notes are here.

Recall that our DP (dynamic programming) algorithm for Knapsack takes time, where was the number of items and was the capacity of our bag. This takes exponential time in the size of the input. We will now show that Knapsack (search version) is NP-complete.

The key will be to show that the following problem, known as the Subset Sum problem, is NP-complete. The knapsack problem is a generalization of Subset Sum so it’ll follow as an easy corollary that knapsack-search is NP-complete.

Subset-sum (SS)

Input: numbers and a parameter

Output: A subset of objects where and NO if no such exists.

We assume that each is at most in magnitude. Then the input size is because each of the items takes bits.

Exercise: Find a DP algorithm for this problem that takes time.

Lemma: Subset-sum is NP-complete

Proof:

a) First show that subset-sum is in NP:

Given input and a solution , it takes time to compute and check that this equals .

b) Next, we reduce 3SAT to SS.

Take a 3SAT input with variables and clauses .

Our input for SS will numbers and some :

We make numbers for the literals:

We make numbers for the clauses:

We will write each of our numbers and as an digit number in base 10. Note that the magnitude of each number could be as large as .

We want that (so ). Thus, we want to include exactly one of .

For each variable , we will set digit of and to 1.

For clause , if , set digit of to 1, else if , set digit of to 1.

We set digits 1 to of to 1. We set digits to of to 3.

Now we set our variables as “slacks” to complete the reduction. For each clause , set digit of slack variables to 1.

Since the first digits of are 1, then for each , we can only choose at most one of (because if we choose both, our numbers will sum to 2 in that column instead of 1).

Since the last digits of are 3, then for each clause , we will need to choose at least one number corresponding to a literal in . For instance, if is , then the only numbers that are non-zero in the digit are and . To get this digit to sum to 3, we need at least one of to be included in .

Suppose that we have the following input to 3SAT:

Then this table shows how we create the numbers for our input to SS.

Lemma: SS has a solution 3SAT has a satisfying assignment

Proof:

Take solution for SS. We know that includes or (but not both). If , then set . If then set . Thus, we have an assignment.

If we look at digit , there will be at least 1 literal in being satisfied by construction.

Take a satisfying assignment for . If , then add to , else if , add to . Then digit of our numbers will sum to 1, as desired.

Look at digit . The assignment must satisfy at least one literal of . If exactly one such literal is satisfied, then add and to . If exactly two literals in are satisfied, then add to . If exactly three literals in are satisfied, then do not add or to .

Next, we show that Knapsack-search is NP-complete.

Knapsack-search:

Input: objects with integer weights and integer values , total capacity , and goal .

Output: Subset of where and .

Lemma: Knapsack-search is NP-complete:

a) Knapsack-search is in NP. We showed this in a previous class.

b) SS Knapsack-search. Take your input to SS: . We define the following input to Knapsack-search. For all , we set , and we set $B = V = t$.

A solution to Knapsack-search must obey:

Thus, , so is a solution to Knapsack-search iff is a solution to the SS instance.