How to understand the knapsack problem is NP-complete?

Question

We know that the knapsack problem can be solved in O(nW) complexity by dynamic programming. But we say this is a NP-complete problem. I feel it is hard to understand here.

(n is the number of items. W is the maximum volume.)

Answer 1

It all depends on which parameters you put inside O(...).

If target weight is limited by number W, then problem has O(n*W) complexity, as you mentioned.

But if weights are way too big and you need algorithm with complexity independent of W, then problem is NP-complete. (O(2^n*n) in most naive implementation).

Answer 2

To understand NP-completeness, you have to learn a bit of complexity theory: you ain't gonna get that from SO! However, basically, it's NP-complete because an efficient algorithm for the knapsack problem would also be an efficient algorithm for SAT, TSP and the rest.

As @Nikita points out, the bounded target weight version isn't in NP but in P. That version can't be used to solve any NP-complete problems (efficiently).

Answer 3

you can read this short explanation: http://www.derf.net/knapsack/#KnapNP (The NP-Completeness of Knapsack) i hope it will help you

Answer 4

The trick is: O(nW) looks like a polynomial time, but it is not, it is pseudo-polynomial. Time complexity measures the time that an algorithm takes as function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W but exponential in the length of W - and that's what matters.

Further references:

• http://www.cs.ship.edu/~tbriggs/dynamic/index.html
• http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27

EDIT

The time complexity of the dynamic solution for the Knapsack problem is basically given by a nested loop:

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

Thus, the time complexity is clearly O(nW). What does it mean to increase linearly the size of the input of the algorithm? It means using progressively longer item arrays (so n, n+1, n+2, ...) and progressively longer W (so if W is x bit long, after one step we use x+1 bits, then x+2 bits, ...). But the value of W grows exponentially with x, thus the algorithm is not really polynomial, it's exponential (but it looks like it is polynomial, hence the name: pseudo-polynomial)