HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

Submitted by: @import:stackexchange-cs··
0
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.