Why a knapsack problem is not solvable in a polynomial time with an algorithm using dynamic programming?

Question

I saw this explanation but I still could not fully understand it. If we follow this logic: Suppose some algorithm works in O(n) time, then: Let's assume n = 1000 in binary term (4-bit long) so the time complexity T(n) = O(8) Let’s double the size of input. n = 10000000 (8-bit long) T(n) = O(128) The time increases in exponential term, so it means that O(n) is not a polynomial time?

Answer 1

The question is: "Polynomial as a function of what?". When we determine complexity of algorithms, we usually, but not always, express it as a function of the length of the input. Often, but not always, this length is represented by the letter n. For instance, if you study problems involving graphs, the letter n is often used to denote the number of vertices in the graph, rather than for the length of the input.

In your case, the variable n is the number of items, and variable W is the capacity of the bag.

Thus, the number n is relevant to the complexity; but it is not, in itself, the entire length of the input. Let's call N the real length of the input. Try not to confuse n and N. The complexity of your algorithms will have to be expressed as functions of N, and terms like "linear complexity", "polynomial complexity", "exponential complexity", etc., will always be in reference to N, not n.

What is the length N of the input?

Your input consists in a list of pairs (weight(i), value(i)), followed by the capacity W. Presumably, each item in the bag is allowed to have a weight ranging from 0 to W; and a value ranging from 0 to some max value V. Thus, weights need as many bits as W to be expressed, and values need as many bits as V to be expressed.

If you know a little about logarithms and about writing numbers, you should know that the number of bits required to write a number is proportional to its logarithm. Thus, every weight requires log(W) bits, and every value requires log(V) bits.

Thus: N = n * (log(W) + log(V)).

You can convince yourself that the lengths of W and V are relevant to the complexity. Here all our numbers are integers. But imagine a real world problem. A weight can be expressed in tons, or in grams. 1 ton is the same as 1000000 grams. A value can be expressed in cents, or in tens of thousands of euros. Before inputting our real-world problem into our algorithm, we need to choose our units.

Is your algorithm going to take a longer time to solve the problem, if the weight is expressed in grams rather than in tons?

The answer is yes. Because grams are a million times more precise than tons. So you are asking for a million times more precise answer, when asking the question in grams rather than in tons. Thus the algorithm will take more time to find that solution.

I hope I could convince you that the complexity of the algorithm should be expressed as a function of the actual length of the input, and not just the number of elements.