The Complexity of Recognizing Facets for the Knapsack Polytope
证明了识别背包多面体面是[公式]完全问题，并给出固定系数个数时多项式时间判定算法，对优化理论研究者有参考价值。
The complexity class [Formula: see text] 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 [Formula: see text]-complete. We provide a positive answer to this conjecture. Moreover, despite the [Formula: see text]-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].