93

We know that the knapsack problem can be solved in O(nW) complexity by dynamic programming. But we say this is a NP-complete problem. I feel it is hard to understand here.

(n is the number of items. W is the maximum volume.)

cnhk
  • 1,265
  • 2
  • 12
  • 13
  • [This quora answer](http://www.quora.com/What-is-the-meaning-of-pseudo-polynomial-time-complexity-I-saw-that-Knapsack-runs-in-pseudo-polynomial-time-I-read-about-this-here-Pseudo-polynomial-time-but-I-am-not-able-to-follow-I-want-to-understand-the-concept-of-pseudo-polynomial-running-time-and-how-knapsack-runs-in-pseudo-polynomial-time/answer/Nishanth-Dikkala) uses example that shows very clear reasoning that lead you to a contradiction and understanding of this topic – DanSkeel May 03 '15 at 15:15

7 Answers7

58

O(n*W) looks like a polynomial time, but it is not, it is pseudo-polynomial.

Time complexity measures the time that an algorithm takes as a function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W, but exponential in the length of W — and that's what matters!

More precisely, the time complexity of the dynamic solution for the knapsack problem is basically given by a nested loop:

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

Thus, the time complexity is clearly O(n*W).

What does it mean to increase linearly the size of the input of the algorithm? It means using progressively longer item arrays (so n, n+1, n+2, ...) and progressively longer W (so, if W is x bits long, after one step we use x+1 bits, then x+2 bits, ...). But the value of W grows exponentially with x, thus the algorithm is not really polynomial, it's exponential (but it looks like it is polynomial, hence the name: "pseudo-polynomial").

Further References

nbro
  • 15,395
  • 32
  • 113
  • 196
Giuseppe Cardone
  • 5,323
  • 2
  • 24
  • 30
  • 2
    There's two ways to measure the size of numbers. Given the numbers 10 and 1000, you can say that 1000 is either twice as big (in number of characters) or one hundred times as big. Since the difference is exponential, you can have an algorithm that's polynomial measured against numeric magnitude and exponential measured against number of bits. – David Thornley Oct 11 '10 at 17:57
  • 9
    I don't see the number of bits in the encoding having anything to do with this question at all. I do understand how number of bits plays into the complexity of integer factorization, since the single integer is your "input." However, the numbers `W` and `n` here represent the **number of loop iterations.** You can encode them any way you want, and that loop is still going to iterate `n * W` times. I believe the reason this "pseudo-polynomial" is because `n` is that actual input size, and `W` can be much much larger than `n` so can't fairly be treated as a constant. – The111 Jun 29 '13 at 22:56
  • @The111 : the point of time complexity analysis is not to express just the number of iterations of an algorithm, it is to express the number of iterations as *function of the size of its input*, that's pretty much how it is defined. So you need to know what it means to increase the size of the input variables of the algorithm that you are analyzing to study its time complexity. – Giuseppe Cardone Jul 01 '13 at 17:31
  • Can you point me to the algorithm? The links don't seem to be active anymore. I am interested in *exact* solutions with `N` weights and total sum being `W`. Is this pseudo-polynomial in `W`? – Jus12 Aug 28 '13 at 07:28
  • 4
    To help you understand it __1)__ consider a `for` loop that goes from `1` to `n` (where `n` is the input); in this case when your loop does 10^12 iterations the size of the input is still around 40 bits. The number of iterations are growing faster than the number of bits to encode the input. Time complexity is _not_ linear. __2)__ again, consider a `for` loop that iterates over an input array (with size `n`) from `1` to `n`; in case you have 10^12 iterations then it means your array contains 10^12 items. No. of iterations grow with the same pace as the size of the input. Time compl. is linear. – Zsolt Safrany Nov 15 '14 at 18:35
  • 1
    @ZsoltSafrany What do you mean by "The number of iterations are growing faster than the number of bits to encode the input." – DollarAkshay May 07 '15 at 21:16
  • 1
    @GiuseppeCardone Using that logic a `for` loop going from **1** to **n** is exponential ? – DollarAkshay May 07 '15 at 21:18
  • 4
    @AkshayLAradhya If we consider my example then let's just add one extra bit to the input. With this, we double the number of iterations (an extra 10^12 iterations) but the length of the input got longer by only one. And with the next extra bit we will get an even more extra iterations. And so on. Hence the "the number of iterations are growing faster than the number of bits [needed] to encode the input" where the input represents the number of iterations. Got it? :-) – Zsolt Safrany May 07 '15 at 21:31
  • @GiuseppeCardone Finally for a loop from 1 to n,whats the complexity ? :-) – crackerplace Jul 10 '16 at 20:19
  • @AkshayLAradhya did you confirm on the answer for 1 to n ? – crackerplace Jul 10 '16 at 20:19
  • 2
    The thing that made it click for me was that for the knapsack problem inputs, n is not a number, it is actual things, while W is a number. You can't solve the knapsack problem for weight 10 and number of things 6. You actually need n to be things...an array that grows. The way we represent the SIZE of n (an array of things) is with a number, but the way we represent the SIZE of W (a number) is with bits. – amoffat Mar 12 '17 at 16:50
  • Also the algorithm can be considered in polynomial if W is a polynomial function. (n, n^2, n^3, etc). Also at the same time if the value of W happens to be something like n!, i.e. exponential then not only would the complexity be exponential, it would be worse than brute force which is 2^n – Sanved May 18 '19 at 02:51
  • Do not think W as an integer. Treat it as an array of bits, just like the array of items. Extend the item array by 1, need to run one more loop. Linear. Extend the W array by 1, need to run twice as many loops. Exponential. – user2961927 May 22 '21 at 17:17
36

In knapsack 0/1 problem, we need 2 inputs(1 array & 1 integer) to solve this problem:

  1. a array of n items: [n1, n2, n3, ... ], each item with its value index and weight index.
  2. integer W as maximum acceptable weight

Let's assume n=10 and W=8:

  1. n = [n1, n2, n3, ... , n10]
  2. W = 1000 in binary term (4-bit long)

so the time complexity T(n) = O(nW) = O(10*8) = O(80)

If you double the size of n:

n = [n1, n2, n3, ... , n10] -> n = [n1, n2, n3, ... , n20]

so time complexity T(n) = O(nW) = O(20*8) = O(160)

but as you double the size of W, it does not mean W=16, but the length will be twice longer:

W = 1000 -> W = 10000000 in binary term (8-bit long)

so T(n) = O(nW) = O(10*128) = O(1280)

the time needed increases in exponential term, so it's a NPC problem.

YoEugene
  • 386
  • 3
  • 6
  • 1
    Thanks YoEugene, I finally kind of see the point here! So the point here is really the complexity is exponential to input size, which in this case is the bit length of W. The same thing happens when we discuss checking whether a number N is prime, the input is really the bit length of N, so though we take N steps and complexity O(N), but it is still pseudo-polynomial. On contrast, if we try to find a number in a array of length N, the input actually N, so complexity of O(N) is really linear. – yeelan Oct 04 '15 at 14:32
7

It all depends on which parameters you put inside O(...).

If target weight is limited by number W, then problem has O(n*W) complexity, as you mentioned.

But if weights are way too big and you need algorithm with complexity independent of W, then problem is NP-complete. (O(2^n*n) in most naive implementation).

Nikita Rybak
  • 67,365
  • 22
  • 157
  • 181
  • What about other dynamic programming problem? For example, the longest common subsequence problem can be solved in O(L_1*L_2) time? Can we say it is not polynomial? – cnhk Oct 11 '10 at 15:44
  • @cnhk Looks like it has polynomial complexity, O(n^2). But there're all kinds of DP algorithms, for example the ones working on all subsets of given set (2^n combinations), so I wouldn't say every DP problem can be solved in polynomial time. – Nikita Rybak Oct 11 '10 at 15:56
5

The size of input is log(W) bits for the weight (and O(n) for "value" and "weight" arrays).

So, the input size of weight is j = log(W) (and not mere W). So, W = 2ʲ (as binary is used).

The final complexity is O(n * W)

This O(n * W) can be rewritten as O(n * 2ʲ), which exponential in the size of the input.

So, this solution is not polynomial.

kaushalpranav
  • 1,725
  • 24
  • 39
4

This is because the knapsack problem has a pseudo-polynomial solution and is thus called weakly NP-Complete (and not strongly NP-Complete).

nbro
  • 15,395
  • 32
  • 113
  • 196
Manav Kataria
  • 5,060
  • 4
  • 24
  • 26
0

You can read this short explanation: The NP-Completeness of Knapsack.

nbro
  • 15,395
  • 32
  • 113
  • 196
dfens
  • 5,413
  • 4
  • 35
  • 50
-1

To understand NP-completeness, you have to learn a bit of complexity theory. However, basically, it's NP-complete because an efficient algorithm for the knapsack problem would also be an efficient algorithm for SAT, TSP and the rest.

nbro
  • 15,395
  • 32
  • 113
  • 196
Pontus Gagge
  • 17,166
  • 1
  • 38
  • 51