Recognition of Facets for Knapsack Polytope is DP-complete
share
DP is a complexity class that is the class of all languages that are the intersection of a language in NP and a language in co-NP, as coined by Papadimitriou and Yannakakis. In this paper, we will establish that, recognizing a facet for the knapsack polytope is DP-complete, as conjectured by Hartvigsen and Zemel in 1992. Moreover, we show that the recognition problem of a supporting hyperplane for the knapsack polytope and the exact knapsack problem are both DP-complete, and the membership problem of knapsack polytope is NP-complete.
READ FULL TEXT