The DP for 0/1 knapsack runs in O(nW). Why is this called pseudo-polynomial rather than polynomial?
AW is encoded in O(log W) bits, so O(nW) is exponential in the input's bit length
Bthe DP table has 2^n cells, not nW
Cknapsack is in P, so any polynomial algorithm is called pseudo-polynomial
Dthe time depends on the number of items, not the capacity
Answer & Solution
Correct answer: A. W is encoded in O(log W) bits, so O(nW) is exponential in the input's bit length
O(nW) looks polynomial in W as a number, but in algorithmic input size W is written in O(log W) bits. So 2^(log W) = W, meaning the running time is exponential in the BIT length of W. This is the textbook definition of pseudo-polynomial. The other options confuse cell count, complexity class definitions, or which input parameter dominates.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for