Lesson 3

The table has roughly \(nB\) states. If \(m=\max_{i} m_{i}\), then the direct recurrence tries up to \(m+1\) choices in every state, so its running time is \(O(nBm)\). This is a good exact algorithm when the budget is moderate.

But it is not polynomial in the ordinary input size. The number \(B\) is written using only about \(\log_{2} B\) bits. If \(B=10^{12}\), the input line containing \(B\) is short, but a table with \(10^{12}\) columns is hopeless. Algorithms of this kind are called pseudo-polynomial: polynomial in the numerical value of the budget, not in the number of bits needed to write it.