The Interval Subset Sum Problem

The transformation of bounded integer variables to binary ones has been considered as a solved problem for long. It is most of the time overlooked that the usual transformation is unacceptable in the case of the Knapsack problem. In this paper, all possible solutions to this problem are characterized. The characterization means that a newly defined decision problem (Interval Subset Sum) is polynomially solvable. In addition the Subset Sum Search problem and a modification of the Kth Largest Subset problem are shown to be polynomially solvable on the class of problems where the answer to the Interval Subset Sum question is ‘yes’.