Abstract
Already 30 years ago, Chv\'atal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules.
We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to: use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution.
Correction: As observed by Hans Ulrich Simon, in Theorem 6 we need that every two vectors in S differ in at least two positions. This ensures that every path accepting a vector in S must test all n variables. Then the last sentence in the proof of Claim 7 is true.