Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution
As you're aware, "polynomial time" means that there is a polynomial&nbsp;$p$ such that the running time on input&nbsp;$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&nbsp;$W$.  Since each weight and each value must take at least one bit to write down, we know that $n&lt;|X|$. But $W$&nbsp;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&lt;|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.)