Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

Question

This question already has an answer here:

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why? (1 answer)

Closed 9 years ago.

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W,ドル so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n,ドル doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?

• Raphael: Buzzword; pseudopolynomial.
• Kaveh: Also see Knapsack problem — NP-complete despite dynamic programming solution? and Why not to take the unary representation of numbers in numeric algorithms?

Answer 1

When we say polynomial or exponential, we mean polynomial or exponential in some variable.

$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input.

This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their weights), the input of the knapsack problem is $n$ numbers $\leq W$. Each number is represented with $\log W$ bits, and there are $n$ numbers, so the size of the instance is $n\log W$.

This makes $nW$ not polynomial in the size of the instance, since $W$ is exponential in $\log W$.

However, (coming back to your example about sorting) an instance for sorting consists of $n$ elements to be sorted, and representing these takes at least $n$ bits (and probably a bit more, since the elements themselves are probably bigger than 1ドル$ bit each). We can represent the number $n$ using $\log n$ bits, but we can't represent $n$ things using $\log n$ bits.

The main difference is that $W$ represents a number in the input, while $n$ represents "the number of things".

Note that if we were to "cheat", we could represent $W$ using $W$ bits if we used a unary encoding. This version of the problem is technically polynomial, but really only because we were deliberately being less efficient.

It turns out that there is a whole class of Strongly NP-Hard Problems, which are still NP-hard even when the input is represented in unary format. But Knapsack is not one of these problems.

• Raphael: This question may be a duplicate. In case it gets closed as such, you may want to check if you want to repost your answer on that other question.
• David Richerby: @Raphael Doh. I'll not repost my answer, since it's already covered by Tom's answer to the other question. (Well, and by his answer to this one, too, but I wanted to make what I think is the main point more succinctly.)
• Raphael: @DavidRicherby I think it's useful to gather multiple answers in the same place. More useful than letting them rot at some duplicate, for that matter.
• Tom van der Zanden: Well, oops. I suppose I should have noticed that this is a duplicate...

Answer 2

I have read that one needs $\lg ⁡W$ to represent $W$ so it is exponential-time. But, I don't understand, also one needs $\lg ⁡n$ to represent $n,ドル no?

This is a great question. You need to look at what the input actually is. The input consists of $n$ items, each of which has a weight $w_i$ and value $v_i,ドル plus the capacity $W$ of your knapsack.

Each of the $w_i$w, the $v_i$s and $W$ is a number, written in binary. In particular, each $w_i$ and $v_i$ must be at least one bit, so the length of the input is at least $n$ bits (well, even 2ドルn$ bits). You're absolutely correct that it takes $\log n$ bits to write $n$ in binary and $\log W$ bits to write $W$. But the point is that $n$ isn't written out in binary as part of the input.

• user12859: I think the points "is that $n$ isn't" just "written out in binary as part of the input", since the analysis would apply even if it was "written out in binary as part of the input". ​ ​
• DollarAkshay: So why isnt n written in binary ?
• David Richerby: @AkshayLAradhya You don't write $n$ in the input at all. You just write a list of items, and $n$ is the number of items in that list. Writing $n$ as well (in binary or unary) wouldn't make any asymptotic difference to the length of the input.