398. Knapsack has an O(nW) DP. Why is it still NP-complete? What does pseudo-polynomial mean?
HardComplexity classes
Show model answer
Complexity is measured against input length in bits. The capacity W takes only about log₂ W bits, so O(nW) is O(n · 2^(bits of W)), exponential in the input size. An algorithm that is polynomial in the numeric values (rather than their bit lengths) is called pseudo-polynomial. If numbers were written in unary, the input would be W long and the DP would be polynomial.
Problems like knapsack, subset sum and partition are weakly NP-complete: hard only because numbers can be huge. Strongly NP-complete problems such as 3-partition, bin packing and TSP remain hard even when numbers are bounded by a polynomial in n. The same encoding point explains why trial division for primality, O(√N), is exponential in the number of digits.