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. Commented Oct 28, 2014 at 19:25
• See also here, here and here (duplicate?). Commented Oct 29, 2014 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. Commented Oct 29, 2014 at 6:33
• If your knapsack has a size of say 6,345,987 that's seven digits. The size of the knapsack is over 6 million, the size of the problem is just seven digits. Commented Oct 19, 2019 at 15:46

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.

Because you normally would not encode the sizes unary. Note that the number "100" would need 100 bit to encode unary (as opposed to the normal 7 bit), so the size of your Knapsack problem would be gigantic, and relative to the then-gigantic size the runtime would not be that bad.

• Doesn't what you're saying suggest it is $P$?
– user8722
Commented Oct 28, 2014 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. Commented Oct 28, 2014 at 19:19
• Just remember: If I increase your problem size exponentially, then of course you will be able to solve it in polynomial time, relative to the exponentially increased input size. Commented Oct 28, 2014 at 19:23
• You might also want to look at Wikipedia's site on Stronly NP-Complete Problems. Commented Oct 28, 2014 at 19:30

Knapsack is a weakly-NP Complete problem because when one encodes it in unary, it runs in polynomial time. However, this does not imply that P=NP it just means that you have artificially increased the input length and so it gives the illusion of running in polynomial time. Also, keep in mind that on small inputs the dynamic programming algorithm appears to be polynomial.

Think about it this way. Say you want to run the algorithm on an instance with $$W=1,000,000$$. When the program will ask you: Please input the value of $$W$$'', are you going to type 7 keys on your keyboard, or 1 million keys?