The Complexity of Recognizing Facets for the Knapsack Polytope

Rui Chen, Haoran Zhu

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 knap…