The complexity of comparing optimal solutions

DOI10.1016/j.ipl.2022.106266OpenAlexW4213433358MaRDI QIDQ2671811

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

Publication date: 3 June 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2022.106266

zbMATH Keywords

computational complexitypolynomial hierarchy\(\Delta_2^p\)-complete\textsc{CompWeightedMaxSAT}\textsc{WeightedMaxSAT}

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• The complexity of optimization problems
• The polynomial-time hierarchy
• The Design of Approximation Algorithms
• Tetris is Hard, Even to Approximate
• On the complexity of unique solutions
• Computational Complexity

This page was built for publication: The complexity of comparing optimal solutions