Sensitivity analysis for knapsack problems: another negative result

AbstractWe answer a question of Blair [Discrete Appl. Math. 81 (1998) 133–139] on the computational complexity of a problem related to the so-called adjacent knapsack problems. We prove that this problem is DP-hard; hence, the problem is at least as difficult as all problems in NP and at least as difficult as all problems in coNP