How to understand the knapsack problem is NP-complete?

Question

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

Nonjuror

This quora answer uses example that shows very clear reasoning that lead you to a contradiction and understanding of this topic – Duplex

Answer 1

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

• http://www.cs.ship.edu/~tbriggs/dynamic/index.html
• http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27

Cloak

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. – Crosscut

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. – Dragoman

@Dragoman : 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. – Cloak

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? – Dielle

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. – Inhalator

@ZsoltSafrany What do you mean by "The number of iterations are growing faster than the number of bits to encode the input." – Audwen

@GiuseppeCardone Using that logic a for loop going from 1 to n is exponential ? – Audwen

@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? :-) – Inhalator

@GiuseppeCardone Finally for a loop from 1 to n,whats the complexity ? :-) – Sladen

@AkshayLAradhya did you confirm on the answer for 1 to n ? – Sladen

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. – Greyso

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 – Arrangement

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. – Shericesheridan

Answer 2

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.

Carolyncarolyne

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. – Impetrate

Answer 3

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

Glazunov

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? – Nonjuror

@Nonjuror 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. – Glazunov

Answer 4

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.

Fogdog

Answer 5

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

Badgett

Answer 6

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

Bauer

Answer 7

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.

Geraint