Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution

All the explanations for why the $O(nW)$ DP algorithm that solves the Knapsack Problem is NOT polynomial repeat the same thing: it is the length (in bits) of the input that matters, not its value/magnitude. The solution has the following structure:

# some preprocessing
for i in range(n):
    for w in range(W):
        # compute stuff

They repeat the same example: $W=10_2=2$, but $W=100_2=4$, i.e. every extra bit doubles the length of $W$. Here's my confusion

• Why can't I apply the same logic for $n$?

As you're aware, "polynomial time" means that there is a polynomial $p$ such that the running time on input $X$ is at most $p(|X|)$.

An input to the knapsack problem consists of a list of $n$ weights, a list of $n$ values and a maximum weight $W$. Since each weight and each value must take at least one bit to write down, we know that $n<|X|$. But $W$ is written in binary and you can easily produce an instance where, say, $W$ has bit-length $|X|/2$. In such an instance, the running time of $nW$ is about $|X|2^{|X/2|}$, which isn't polynomial.

The key point that you've missed is that $n<|X|$ because, effectively, the input specifies $n$ in unary. (That is, if the weights are $1,3,2,5,2,2$, then $n$ is basically the number of commas, modulo the usual off-by-one error.)

StackExchange Computer Science Q#111227, answer score: 4