The complexity of comparing optimal solutions

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

*此作品的通信作者

研究成果: Article同行評審

摘要

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

原文English
文章編號106266
期刊Information Processing Letters
177
DOIs
出版狀態Published - 8月 2022

指紋

深入研究「The complexity of comparing optimal solutions」主題。共同形成了獨特的指紋。

引用此