The Complexity of Recognizing Facets for the Knapsack Polytope

The complexity class ${\mathtt{D}}^{\mathtt{p}}$ is the class of all languages that are the intersection of a language in NP and a language in co-NP. It was conjectured that recognizing a facet for the knapsack polytope is ${\mathtt{D}}^{\mathtt{p}}$-complete. We provide a positive answer to this conjecture. Moreover, despite the ${\mathtt{D}}^{\mathtt{p}}$-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.

Funding: The research of R. Chen was supported by the National Natural Science Foundation of China [Grant 72501249].