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

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?

• Keep in mind that DP is polynomial in the "table size". The table is exponentially large for Knapsack (see Kaveh's answer). – Raphael Mar 31 '12 at 7:13

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.

• 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? – Strin Apr 1 '12 at 16:20
• @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.) – Kaveh Apr 2 '12 at 1:21
• 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? – Char May 16 '12 at 9:13
• @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. – The111 Jun 29 '13 at 23:09
• @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. – Kaveh Jun 30 '13 at 5:45

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

• Created an account here just to say thank you so much! Only after your example I've finally understood it. – Inoryy Mar 6 '14 at 6:03
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}$.