The complexity of lifted inequalities for the knapsack problem

It is well known that one can obtain facets and valid inequalities for the knapsack polytope by lifting simple inequalities associated with minimal covers. The authors study the complexity of lifting. They show that recognizing integral lifted facets or valid inequalities can be done in O(n²) time, even if the minimal cover from which they are lifted is not given. The authors show that the complexities of recognizing nonintegral lifted facets and valid inequalities are similar, respectively, to those of recognizing general (not necessarily lifted) facets and valid inequalities. Finally, they show that recognizing valid inequalities is in co-NPC while recognizing facets is in D^p. The question of whether recognizing facets is complete for D^p is open.