Why is the knapsack problem pseudo-polynomial?
complexity-theory, dynamic-programming, knapsack-problem, language-agnostic
Solution
The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial.
Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the computational runtime uses the factor 1,000,000,000,000 which is O(240).
So the runtime is more accurately said to be O(N.2bits in W), which is exponential.
Also see:
- How to understand the knapsack problem is NP-complete?
- The NP-Completeness of Knapsack
- Complexity of dynamic programming algorithm for the 0-1 knapsack problem
- Pseudo-polynomial time
Problem
I know that `Knapsack` is NP-complete while it can be solved by DP. They say that the DP solution is `pseudo-polynomial`, since it is exponential in the "length of input" (i.e. the numbers of bits required to encode the input). Unfortunately I did not get it. Can anybody explain that `pseudo-polynomial` thing to me slowly ?