Knapsack problem -- NP-complete despite dynamic programming solution?

Question

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right?

I have read it is actually an NP-complete problem, though, which would mean that solving the problem in polynomial problem is probably impossible.

Where is my mistake?

• Raphael: Keep in mind that DP is polynomial in the "table size". The table is exponentially large for Knapsack (see Kaveh's answer).

Answer 1

Knapsack problem is $\sf{NP\text{-}complete}$ when the numbers are given as binary numbers. In this case, the dynamic programming will take exponentially many steps (in the size of the input, i.e. the number of bits in the input) to finish $\dagger$.

On the other hand, if the numbers in the input are given in unary, the dynamic programming will work in polynomial time (in the size of the input).

This kind of problems is called weakly $\sf{NP\text{-}complete}$.

$\dagger$: Another good example to understand the importance of the encoding used to give the input is considering the usual algorithms to see if a number is prime that go from 2ドル$ up to $\sqrt{n}$ and check if any of them divide $n$. This is polynomial in $n$ but not necessarily in the input size. If $n$ is given in binary, the size of input is $\lg n$ and the algorithm runs in time $O(\sqrt{n}) = O(2^{\lg n/2})$ which is exponential in the input size. And the usual computational complexity of a problem is w.r.t. the size of the input.

This kind of algorithm, i.e. polynomial in the largest number that is part of the input, but exponential in the input length is called pseudo-polynomial.

• Strin: But think about the objects to be put in the knapsack. The objects need to be input and such an input must be polynomial with the number of objects. If objects are many enough, then the input is polynomial with the size of the problem. So why cannot I say that Knapsack Problem is P problem in terms of table size? Am I wrong?
• Kaveh: @Strin, no, a small number of objects can be sufficient to feel a large knapsack, e.g. if the size of the Knapsack is $m,ドル one objeact of size $m$ is sufficient. The size of the input is roughly 2ドル\lg m,ドル much smaller than $m$. (I am assuming that we are talking about 0-1 Knapsack.)
• Char: Can you break the input down into smaller inputs whose binary encoding has a size that finishes the algorithm in polynomial time then combine the solutions?
• The111: @Kaveh "The size of the input is roughly 2 lg m" I don't understand where you get that part from. The relationship between m (pack size) and n (num of items) is totally unknown, right? And re "when the numbers are given as binary numbers"... but couldn't you say that for anything? With most algorithms, we talk about input size in base 10. Why talk about binary here? And whether you encode in binary, octal, decimal, etc... the actual number of times you iterate through your main algorithm loop is directly dependent on both n and W.
• Kaveh: @The111, I think it is better if you post that as a new question that and I will post an answer. I think your question is more fundamental and there comments are not very related to this question.

Answer 2

The main confusion lies in the difference between "size" and "value".

"Polynomial Time" implies polynomial w.r.t the size of input.

"Pseudopolynomial Time" implies polynomial w.r.t the value of the input. It can be shown (below) that this is equivalent to being exponential w.r.t the size of the input.

---

In other words: Let $N_{size}$ represent the size of the input and $N_{val}$ represent the value of the input.

Polynomial Time: $O(N_{size}^x)$ for $x\in\mathbb{N}$

Pseudopoly. Time: $O(N_{val}^x)$ for $x\in\mathbb{N}$

Now, the knapsack problem has a pseudopolynomial, not polynomial, solution because the dynamic programming solution gives a running time dependent on a value -- i.e. $O(nW),ドル where $W$ is a value representing the max capacity.

Now, a value can be converted into a size by representing it in terms of # of digits it takes to represent it. $N_{size}=Log_b(N_{val})$ tells you how many digits are needed to represent $N_{val}$ using base $b$. This can be solved for $N_{val}$ to give:

$$N_{val}=b^{N_{size}}$$

Plugging this into the pseudopolynomial time definition shows that it is exponential w.r.t $N_{size}$:

Pseudopoly. Time: $O(b^{xN_{size}})$ for $b, x\in\mathbb{N}$

• Inoryy: Created an account here just to say thank you so much! Only after your example I've finally understood it.
• Muhammad Razib: Your answer beats everyone, bravo!
• Amen: To add to this great answer we can say that if we change the W from 100 to 101 the size of the problem is not increased, the size is increased if we add another bit to W which makes it twice as big, so the table would have twice as much rows and therefore with increasing the size by one, the problem time is doubled, that is why it's exponential.
• DollarAkshay: @bcorso Suppose you are given a value N. And you had to find the sum of numbers from 1 to N and you used the for loop method, that would be a pseudopolynomial Time algorithm?
• DollarAkshay: But with that logic a simple for loop with value N is not linear but exponential ?

Answer 3

The Knapsack problem as defined in Karp's paper is NP-Complete since there is a reduction from other NPC problem (Exact Cover, in this case) to Knapsack. This means that there is no polynomial algorithm that can solve all instances of the Knapsack problem, unless $\text{P}=\text{NP}$.

There are, however, different variants (e.g., 0-1 Knapsack and others) that may or may not have polynomial-time solutions or good approximations. But this is not the same as the general Knapsack problem. Also, there might be efficient algorithms that work for specific (families of) instances, but these algorithms will take longer on other instances.

• Sid Sarasvati: logged in just to downvote, the questions asks exactly the conundrum posed by p = np theory depiste the illusion of knapsack running in poly time using dynamic programming. Putting the theory that knapsack cannot be P because it is NP doesn’t help