[snom370]

Sure seems optional to me, he should have used must. :)

[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.)