[eru]

And he did not say polynomial in what.

I can make the program run polynomial in the size of sum of the input numbers. (I.e. pseudo-polynomial in the input.)