why 0/1 knapsack using dynamic programming is not polynomial time algorithm

Question

I have difficuities understanding why 0/1 knapsack using dynamic programming is not polynomial time solvable. Similar question had been asked here. Why is the knapsack problem pseudo-polynomial?. Someone gave explanation, but I still don't get why should we consider the binary representation for the weight input. How about n, if it's considered in binary representation, can I say it's exponentional to number of the items? Similarly, for any other polynomial time algorithms I can claim them having exponentional time complexity, because every input are represented in binary digits in computer. I know I were wrong. Can someone point out why in a easy understanding way? Thanks in advance.

Answer 1

Given the knapsack problem with the following inputs: n item values v_i, n weights w_i and a capacity K value (represented by k bits), we have:

The input size in bits is N = 2n*64 + k.

Therefore, the bit complexity of the knapsack DP solution is O(N) = O(n*2^k) (the constant factor 64 is ignored)

The following assumption is implied in the above calculations: each weight w_i and each value v_i can be represented with a word with max size of 8 bytes or 64 bits

To elaborate further:

If the capacity is doubled (K' = 2K or k'=k+1), the inputs still contain n values v_i, n weights w_i and a capacity value K' (represented by k+1 bits). Therefore, the input size in bits is N' = 2n*64 + k + 1 = N+1. In conclusion, the number of bit operations is doubled when k is increased by one => O(N) is exponential w.r.t. k and pseudo-polynomial w.r.t. K

If the number of items is doubled (n' = 2n), the inputs now contain 2n item values v_i, 2n weights w_i and a capacity value K. Therefore, the input size in bits is N' = 2*2n*64 + k. In conclusion, the number of bit operations is doubled when n is doubled => O(N) is polynomial w.r.t. n

References on bit complexity and word complexity:

http://en.wikipedia.org/wiki/Context_of_computational_complexity

Book: A Programmer's Companion to Algorithm Analysis - Section 2.2

Upvotes: 2

Answer 2

A very simple way of thinking about it is that if you double the limit, the size of the input only increases by one bit (since the limit is part of the input), while the run time is doubled. That is clearly exponential behavior with respect to the input size.

However, while doubling the number of items also doubles the run time, it also doubles the size of the input items, so that part of the relationship between input size and run time is only linear.