Why rocket 0/1 using dynamic programming is not a polynomial time algorithm

Question

I have problems understanding why ranking 0/1 using dynamic programming is not a solvable polynomial time. A similar question was asked here. Why is the backpack problem pseudopolynomial? . Someone gave an explanation, but I still do not understand why we should consider the binary representation for entering the weight. What about n if it is taken into account in binary representation, can I say this exponentially for the number of elements? Similarly, for any other polynomial time algorithms, I can argue that they have complex time complexity, since each input is represented by binary numbers on a computer. I know that I was wrong. Can anyone point out why this is easy to understand? Thanks in advance.

Answer 1

A very simple way to think that if you double the limit, the input size increases by only one bit (since the limit is part of the input), and the execution time doubles. This is clearly exponential behavior relative to input size.

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

Answer 2

Given the problem with a backpack with the following inputs: n values ​​of elements v _i , n weights w _i and the value of capacitance K (represented by k bits), we have:

The input size in bits is N = 2n * 64 + k. Therefore, the bit-bit complexity of the DP backpack solution is O (N) = O (n * 2 ^k ) (constant factor 64 is ignored)

In the above calculations, the following assumption is implied: each weight w _i , and each value v _i can be represented by a word with a maximum size of 8 bytes or 64 bits

Further clarify:

If the capacitance doubles (K '= 2K or k' = k + 1), the inputs still contain n values ​​v _i , n weights w _i and the capacitance 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 doubles when k increases by one => O (N) exponentially wrt k and the pseudo-polynomial wrt K

If the number of elements doubles (n '= 2n), the inputs now contain 2n elements v _i , 2n weights w _i and a capacitance value K. Therefore, the input size in bits is N' = 2 * 2n * 64 + k. In conclusion, the number of bit operations doubles when n doubles => O (N) is the polynomial wrt n

References to bit complexity and word complexity:

http://en.wikipedia.org/wiki/Context_of_computational_complexity Book: Companion Programmer for Algorithm Analysis - Section 2.2