The complexity of packing
The knapsack problem gives one a set of items, each with a weight and value. Given a value V and maximum weight W, can a value of at least V be obtained by picking objects from the set such that the total weight does not exceed W?
An algorithm has been found that can compute the solution to this problem in time, where N is the number of items to choose from and S is the sum of the weights of those items.
Suppose this is in fact the optimal solution to knapsack, that is, no algorithm can solve this problem faster than . What complexity class does the problem belong to?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The Knapsack problem is clearly in NP. Given a solution to the knapsack problem - i.e. a list of objects that match the criteria, we can easily verify that the sum of the values is ≥ V and the sum of weights is ≤ W .
So the choices are really the following two options:
The problem asserts that there does not exist any algorithm that can solve this problem faster than Θ ( n ∗ S ) , where S is the sum of the weights of all the items. Since S can be arbitrarily large (by simply choosing large weights), the function n ∗ S is larger than any polynomial function. So this assertion implies that there is no polynomial time algorithm to solve this problem. Hence the problem is not in P.
That gives us the answer to this problem: NP (and not P)