Why is the dynamic programming algorithm of the knapsack problem not polynomial?

Problem Detail: 

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W$, so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n$, doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?

Asked By : Kaalouss

Answered By : Tom van der Zanden

When we say polynomial or exponential, we mean polynomial or exponential in some variable.

$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input.

This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their weights), the input of the knapsack problem is $n$ numbers $\leq W$. Each number is represented with $\log W$ bits, and there are $n$ numbers, so the size of the instance is $n\log W$.

This makes $nW$ not polynomial in the size of the instance, since $W$ is exponential in $\log W$.

However, (coming back to your example about sorting) an instance for sorting consists of $n$ elements to be sorted, and representing these takes at least $n$ bits (and probably a bit more, since the elements themselves are probably bigger than $1$ bit each). We can represent the number $n$ using $\log n$ bits, but we can't represent $n$ things using $\log n$ bits.

The main difference is that $W$ represents a number in the input, while $n$ represents "the number of things".

Note that if we were to "cheat", we could represent $W$ using $W$ bits if we used a unary encoding. This version of the problem is technically polynomial, but really only because we were deliberately being less efficient.

It turns out that there is a whole class of Strongly NP-Hard Problems, which are still NP-hard even when the input is represented in unary format. But Knapsack is not one of these problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52763