The complexity of comparing optimal solutions

Da Ren Chen, Min Zheng Shieh*, Shi-Chun Tsai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Δ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.

Original languageEnglish
Article number106266
JournalInformation Processing Letters
StatePublished - Aug 2022


  • Computational complexity
  • Polynomial hierarchy
  • Δ-complete


Dive into the research topics of 'The complexity of comparing optimal solutions'. Together they form a unique fingerprint.

Cite this