| Article ID: | iaor20001649 |
| Country: | Netherlands |
| Volume: | 92 |
| Issue: | 2/3 |
| Start Page Number: | 247 |
| End Page Number: | 251 |
| Publication Date: | Jun 1999 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Woeginger Gerhard J. |
| Keywords: | knapsack problem |
We answer a question of Blair 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.