I asked my Advanced Algorithms professor recently if we could solve the coin change problem (least number of coins necessary to make change for S cents using denominations d1, d2, ... dk). I thought this might be possible using something like the least common multiple of the denominations to find a subset of answer that could be used to determine the whole answer, independent of the size of S.
My professor said that this is actually a very complicated problem, and there was a paper in the 90's or 2000's to that demonstrated this solution. He couldn't remember the reference for this paper, though. Could anyone provide the reference? I would be very appreciative.