patternMinor
Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?
Viewed 0 times
problemwhythepolynomialalgorithmoneforknapsacknot
Problem
On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to $\log W$, where, I believe, $W$ is the size of the knapsack. Why is the size of the input related logarithmically to $W$?
Solution
Polynomial time means that the running time is bounded by a polynomial in the length of the input. The running time here is bounded by $nW$. $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$ bits, you can write a number up to $2^\ell$ so $W$ is potentially exponential in the length of the input, not polynomial.
Context
StackExchange Computer Science Q#32414, answer score: 7
Revisions (0)
No revisions yet.