Some complexity issues in a class of knapsack problems: What makes a knapsack problem ‘hard’?

The authors propose a new class of knapsack problems by assuming that the sizes of the items to be put into a knapsack are known to be elements of a given subset S of the positive integers Z’+. The set S is treated as a parameter. It is shown that the family of knapsack problems obtained by varying the parameter S in the power set of Z’+ contains polynomially solvable problems and NP-complete problems, even when S is restricted to the class of polynomially recognizable sets.