1
$\begingroup$

My question is why O(nW) at the knapsack problem is pseudo-polynomial.

I read lots of the explanation at stackoverflow, But I don't really understand it. (https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time, https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668)

The core thing is why we have to think only 'W' as 'logW' bits input, not 'n' as 'log n' bits.

The many explanation said that 'W' is integer but 'n' is just the number of item. Therefore only 'W' size is proportional to 'logW'.

I think this logic have to be applied to 'n'.

Assuming that we are numbering the items from 1 to n, for differentiating the items,

we have to count the numbers from 1 to n.

I think it is the same that the loop does iteration for W times.

Therefore I think it is same with 'W' because this counting also need 'log n' bits.

What do I mis-understand at this problem?

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Here is how you encode the input:

  • Weight and value of item 1.
  • Weight and value of item 2.
  • ...
  • Weight and value of item $n$.
  • $W$.

Suppose that the weight and value are integers, are at most $M$, and both are encoded in binary, as is $W$. Then the length of the encoding is $$ \Omega(n + \log W), O(n\log M + \log W). $$ Hopefully this clarifies the difference between $n$ and $W$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. But I have a question. but I'm confused yet. Assume n is same with W. Then n items list iteration is same with W times iteration, in terms of the number of iteration. is it right? $\endgroup$
    – nimdraks
    Commented Apr 22, 2020 at 14:56
  • $\begingroup$ The input length is proportional to $n + \log W$ (neglecting $M$). Therefore counting from $1$ to $n$ takes polynomial time, but counting from $1$ to $W$ could take exponential time, if $W$ is very large compared to $n$. $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2020 at 14:57
  • $\begingroup$ Then is it right? Time complexity is actually decided by the input length(input size) in binary encoding. At 'W', its size is logW due to its binary encoding but in the 'n' case, it is just n because it is just a list. it's like unary encoding. $\endgroup$
    – nimdraks
    Commented Apr 22, 2020 at 15:05
  • $\begingroup$ The time complexity depends on the encoding. We usually use binary encoding, in which case what you wrote is correct. If $W$ is encoded in unary then we do get a polynomial time algorithm. This is the real meaning of "pseudo-polynomial time algorithm". $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2020 at 15:06
  • $\begingroup$ I finally understand it. I love you. thank you so much! $\endgroup$
    – nimdraks
    Commented Apr 22, 2020 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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