QCSP Monsters and the Demise of the Chen Conjecture

Zhuk, Dmitriy; Martin, Barnaby

Abstract

We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Γ, QCSP(Γ), where Γ is a finite language over 3 elements which contains all constants. In particular, such problems are either in P, NP-complete, co-NP-complete or PSpace-complete. Our classification refutes the hitherto widely-believed Chen Conjecture.
Additionally, we show that already on a 4-element domain there exists a constraint language Γ such that QCSP(Γ) is DP-complete (from Boolean Hierarchy), and on a 10-element domain there exists a constraint language giving the complexity class ΘP2.
Meanwhile, we prove the Chen Conjecture for finite conservative languages Γ. If the polymorphism clone of Γ has the polynomially generated powers (PGP) property then QCSP(Γ) is in NP. Otherwise, the polymorphism clone of Γ has the exponentially generated powers (EGP) property and QCSP(Γ) is PSpace-complete.

Citation

Zhuk, D., & Martin, B. (2022). QCSP Monsters and the Demise of the Chen Conjecture. Journal of the ACM, 69(5), 1-44. https://doi.org/10.1145/3563820

• Journal Article Type: Article
• Acceptance Date: Jul 9, 2022
• Online Publication Date: Oct 28, 2022
• Publication Date: Oct 31, 2022
• Deposit Date: Jan 9, 2025
• Publicly Available Date: Jan 10, 2025
• Journal: Journal of the ACM
• Print ISSN: 0004-5411
• Electronic ISSN: 1557-735X
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 69
• Issue: 5
• Article Number: 35
• Pages: 1-44
• DOI: https://doi.org/10.1145/3563820
• Public URL: https://durham-repository.worktribe.com/output/3328986