There is something I don't understand. In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we ...
The addition algorithm is polynomial (as far as I know, perhaps I'm wrong). Suppose that $n$ is the number of numbers to be added, and tghe largest one of them is $2^n$. Is this problem still ...
Say I have 2 carts on an infinite railroad, each cart is initially under a lamp. There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between ...
The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input ...