Toward a model for backtracking and dynamic programming

We consider a model (BT) for backtracking algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as interval scheduling, knapsack and satisfiability.