The Complexity of Recognizing Facets for the Knapsack Polytope
arXiv:2211.03311
Abstract
The complexity class DP is the class of all languages that are the intersection of a language in NP and a language in coNP. It was conjectured that recognizing a facet for the knapsack polytope is DP-complete. We provide a positive answer to this conjecture. Moreover, despite the \DP-hardness of the recognition problem, we give a polynomial time algorithm for deciding if an inequality with a fixed number of distinct coefficients defines a facet of a knapsack polytope.