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

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$?

• Problems don't have runtimes. Furthermore, "pseudopolynomial" is the buzzword you want to search for. – Raphael Oct 28 '14 at 19:25
• See also here, here and here (duplicate?). – Raphael Oct 29 '14 at 6:29
• Oh, and some nitpick: "doesn't violate its classification as NP" is an empty statement. Even if the algorithm ran in polynomial time, Knapsack would still be in NP and NP-complete. – Raphael Oct 29 '14 at 6:33

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.
• Doesn't what you're saying suggest it is $P$? – user8722 Oct 28 '14 at 19:14
• Well yes. If you encode the input unary, then it's even in Logspace. But that's just a foul trick; consider for example a knapsack problem for $n=10^{12}$. You would need a terabyte to encode the problem unary! Unary encoding means that you encode the number by a sequence of $1$s. And relative to that GIGANTIC input size the runtime is polynomial. – john_leo Oct 28 '14 at 19:19