Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 16 down vote favorite
3

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?

share|improve this question
1  
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

2 Answers

up vote 15 down vote accepted

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

These kind of problems are 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.

share|improve this answer
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
up vote 5 down vote

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 any instance 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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