The complexity of comparing optimal solutions

Da Ren Chen; Min Zheng Shieh; Shi Chun Tsai

doi:10.1016/j.ipl.2022.106266

The complexity of comparing optimal solutions

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

Δ₂^p 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 Δ₂^p-complete problem. We first prove that COMPWEIGHTEDMAXSAT is Δ₂^p-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 language	English
Article number	106266
Journal	Information Processing Letters
Volume	177
DOIs	https://doi.org/10.1016/j.ipl.2022.106266
State	Published - Aug 2022

Keywords

COMPWEIGHTEDMAXSAT
Computational complexity
Polynomial hierarchy
WEIGHTEDMAXSAT
Δ-complete

Access to Document

10.1016/j.ipl.2022.106266

Cite this

@article{71f26518eda64d5ab8cbaffb69b25cfc,

title = "The complexity of comparing optimal solutions",

abstract = "Δ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.",

keywords = "COMPWEIGHTEDMAXSAT, Computational complexity, Polynomial hierarchy, WEIGHTEDMAXSAT, Δ-complete",

author = "Chen, {Da Ren} and Shieh, {Min Zheng} and Tsai, {Shi Chun}",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = aug,

doi = "10.1016/j.ipl.2022.106266",

language = "English",

volume = "177",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

}

TY - JOUR

T1 - The complexity of comparing optimal solutions

AU - Chen, Da Ren

AU - Shieh, Min Zheng

AU - Tsai, Shi Chun

PY - 2022/8

Y1 - 2022/8

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

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

KW - COMPWEIGHTEDMAXSAT

KW - Computational complexity

KW - Polynomial hierarchy

KW - WEIGHTEDMAXSAT

KW - Δ-complete

UR - http://www.scopus.com/inward/record.url?scp=85125495299&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2022.106266

DO - 10.1016/j.ipl.2022.106266

M3 - Article

AN - SCOPUS:85125495299

SN - 0020-0190

VL - 177

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106266

ER -

The complexity of comparing optimal solutions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this