Δ2p is the complexity class of languages recognizable by deterministic Turing machines in polynomial time with an NP oracle. OptP is the class of functions computable by taking the maximum (or minimum) value of some function over a set of feasible solutions. In this work, we show that comparing the optimal values of two instances of some OptP-complete problems is Δ2p-complete problem. We first prove that COMPWEIGHTEDMAXSAT is Δ2p-complete and then generalize it to other OptP-complete problems, where COMPWEIGHTEDMAXSAT is the problem of comparing the optimal values of two instances of WEIGHTEDMAXSAT to determine whether the first optimal value is greater than the second one.
- Computational complexity
- Polynomial hierarchy