2
$\begingroup$

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?)

$\endgroup$
5
$\begingroup$

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

$\endgroup$

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.