Week 12 - Knapsack complexity
We are going to prove that the Knapsack-search is NP-complete. We will do this using the 3-SAT but first going through the Subset-sum problem.
Subset-sum problem
Statement
Link to originalSubset-sum problem
Given positive integers
and , is there a subset where if such a subset exists output it, otherwise return no.
This can be solves using Dynamic Programming in a similar way to the Knapsack problem in
Subset-sum problem is in NP
Statement
Lemma
Subset-sum problem is in NP.
Proof
It is of the format to be a search problem as it either returns a result or it says no such result exists.
Suppose we are given an instance
for and . To verify a solution make the check this takes
Link to originaltime. Therefore this takes polynomial time.
Moreover it is NP-complete.
Subset-sum problem is NP-complete
Statement
Lemma
Proof
We already know the Subset-sum problem is in NP. So we need to show it is NP-hard. To do this we will make a many-one reduction from the 3-SAT problem. We know that 3-SAT is NP-complete giving the desired result.
Suppose we an instance of the 3-SAT problem given by
with variables with and clauses for . Each clause can have at most 3 literals. We will now construct an input to the subset-sum problem that will have
input numbers and a target . We will want to talk about these numbers digits in base 10. i.e. express the number then
is its ‘th digit. For each variable
we will introduce two variables and . Let and . Then we define For each
we define two variables which are identical Lastly we define our target
It is useful to talk about map
where This map is a bijection so it has well defined inverse Observation
Let
then Any sum of the
, , , and can have at most 5 in any digit (as each clause can have at most 3 literals and 2 values from the or ), therefore there is no overflow from one digit to another. We provide this input to the subset-sum problem, this transformation takes
time, so it is polynomial time. Any solution
to the constructed subset-sum problem must have exactly one of or for each as has a 1 in its first digits. Therefore construct assignment for where This takes
to construct, as we just need to iterate through . So can be done in polynomial time. Suppose we have a solution to the constructed subset-sum problem. Then we have a valid assignment by the observation.
When looking at the last
digits of we require a 3 in each position. Therefore for each we have at least one such that therefore and we satisfy clause . Therefore this is a valid solution to the 3-SAT problem
. Suppose we have a valid assignment
to for the 3-SAT problem . Then for each clause
define to be the number of satisfied literals - note . Now define
Consider the sum
For the first digits, as or we have . For the last
digits, we have and which gives a 3 in these digits. So
is a solution to our constructed subset-sum problem. Therefore this is a valid many-one reduction and we have subset-sum problem is NP-hard and thus NP-complete.
Link to original
Knapsack problem
This subset-sum problem is very similar to the Knapsack-search problem so we have the following.
Knapsack-search is NP-complete
Statement
Lemma
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
Link to original