My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?
I understand the argument of the answer above. Also the answer is given in this book ''The Desing of Approximation Algorithms'' that I am reading. In [pp. 67, §2], the authors said:
Algorithm 3.1 takes $O(n\cdot \min(B, V))$ time. This is not a polynomial-time algorithm, since we assume that all input numbers are encoded in binary; thus, the size of the input number $B$ is essentially $\lg B,ドル and so the running time $O(n\cdot B)$ is exponential in the size of the input number $B,ドル not polynomial. $\cdots$
I understand that $O(n\cdot B)$ is exponential in the size of the input number $B,ドル but also, in my point of view (which is wrong), $O(n\cdot B)$ is exponetial in the size of the input number $n,ドル i.e., the size of the input $n$ is $\lg n$. Why not? (If I were to represent $n$ in binary I would take $\lg n$ size, no?)
1 Answer 1
$n$ is not part of the input, $n$ denotes the number of objects in the input.
The input consists of the capacity of the knapsack, a list of objects, each with a value and weight. If there are $n$ objects in the instance then the size of the instance is at least $n$ since each object needs to be represented (with at least one bit). Therefore $n$ is polynomial in the size of the input.
In general, the size of the input (if all weights and values are at most $B$) will be $O(n \log B),ドル since there are $n$ objects to represent and representing an object (which is two numbers at most $B$) will take around 2ドル\log B$ bits.