About the pseudo polynomial complexity of the KnapSack 0/1 problem

Question

I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some doubts.

A question that frequently arises when discussing the complexity of the dynamic programming solution for the KS problem is something like ¿Why $O(n \cdot W)$ is not considered polynomial?.

The common answer is that, by definition, we are concerned with the running time of an algorithm as a function of the size of the input. So, while is correct to say the running time is bounded by a polynomial in the value of $W$, is not polynomial in the size of $W$, because in fact what we have is $O(n \cdot 2^W)$.

Here we can also ask ¿Why not $O(2^n \cdot 2^W)$?, i.e. by the same reasoning $n$ should also be exponential in the length of the input. But the "trick" is that it seems $n$ is usually (always?) not considered part of the input at all. Instead, the input is (by convention i guess) just a list of $n$ weights, a list of $n$ values, and capacity $W$. Indeed, we don't need $n$ itself in the input.

Questions:

1. Suppose we have $n$ itself in the input, as nothing stops me of doing it in this way. The algorithm loops from $0$ to $n$ in the same way it loops from $0$ to $W$. Now, is correct to say the running time is $O(2^n \cdot 2^W)$ ?.
2. But if (1) is the correct, i dont think this algorithm with $n$ in the input have the same asymptotic behavior as the common one. How $O(2^n \cdot 2^W)=O(2^{n+W})$ compare with $O(n \cdot 2^W)$ ?.
3. Consider the usual naive recursive algorithm for the KS 0/1 problem. This is said to be $O(2^n)$, because in the worst case two recursive calls on $n-1$ are needed. In this case, $n$ is clearly in the input, but we are considering $n$ as a value when doing the recurrence analysis. So, considering earlier discussion, i'm tempted to say that in fact we have $O(2^{(2^n)})$ which is double exponential and not just exponential ... but does this make sense?

Answer 1

Whether $n$ is "included in the input" or not is irrelevant. No "tricks" are being used to sneakily hide $n$ from the input by implicitly including it as the length of a list.

The input is at least $n$ bits long because it must include a list of all the values and weights of items. If we are not given the values and weights of the items as part of the input, then how are we supposed to solve the problem (if we do not know the weight/value of some items)?

Now, since we know that the input has length (in bits) at least $n$, any running time of the form $n, n^2, n^3,...$ is polynomial in the length of the input.

However, the length of a (reasonable representation of the input) is at most $O(n\log W)$ (assuming the values of the items are on the same order of magnitude as their weights). For every item we must give the weight and value, and this can be done with $\log W$ bits per item (by giving the binary representation of the weight/value).

As Yuval noted, $nW$ is not polynomial in $n\log W$.

It does not matter if we consider the input as the lists only or the lists "together with" $n$. If we also include $n$ explicitly, it just makes the input $\log n$ bits longer. But since the input is already at least $n$ bits long, having $\log n$ extra bits makes no difference.

Answer 2

Suppose that there are $n$ integer weights of magnitude at most $W$. We can encode each weight in $O(\log W)$ bits, and so the total input length (in bits) is $O(n\log W)$. An algorithm is polynomial if its running time is $O((n\log W)^C)$ for some $C$. Dynamic programming runs in $\Theta(nW)$. Unfortunately, $nW$ cannot be bounded by $O((n\log W)^C)$ for any constant $C$.