How to understand the knapsack problem is NP-complete?

algorithm, complexity-theory

Solution

`O(n*W)` looks like a polynomial time, but it is not, it is pseudo-polynomial.

Time complexity measures the time that an algorithm takes as a 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!

More precisely, 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(n*W)`.

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` bits 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").

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

Problem

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.)

Original source