1
$\begingroup$

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?
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think i agree everything you said until the last paragraph. From this, i don't see what is wrong with saying that the algorithm is $O(2^n \cdot 2^W)$ when $n$ is in the input. So, to be clear, are you implying that even if $n$ is in the input, the cost is still $O(n \cdot 2^W)$? $\endgroup$ – fulem Nov 2 '20 at 22:19
  • $\begingroup$ @fulem The algorithm is $O(nW)$. It is not $\Omega(2^n\cdot 2^W)$ and also not $\Omega(n\cdot 2^W)$. $O(nW)$ is the running time of the algorithm. $O(nW)$ is polynomial in $n$ and $W$ but it is not polynomial in the length of the input. $\endgroup$ – Tom van der Zanden Nov 3 '20 at 9:34
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Hi Yuval. I'm afraid i don't see how this answer any of my three questions. Could you, please, elaborate? $\endgroup$ – fulem Nov 2 '20 at 21:14
  • $\begingroup$ Your questions betray a misunderstanding on the relation between $n$, $W$, and the input length in bits. I tried to dispel this confusion in my answer. $\endgroup$ – Yuval Filmus Nov 2 '20 at 21:18
  • $\begingroup$ Ok. But, do you think that my misunderstanding of the relation between $n$ and $W$ in the dynamic programming solution is also the source of confusion for my third question? i.e. that the recursive KS solution is $O(2^{(2^n)})$. $\endgroup$ – fulem Nov 2 '20 at 22:26
  • $\begingroup$ The exhaustive search solution checks $2^n$ subsets. $\endgroup$ – Yuval Filmus Nov 3 '20 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.