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 Θ ???? 2 . Meanwhile, we prove the Chen Conjecture for finite conservative languages Γ. If the polymorphism clone of such Γ 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. (2020, June). QCSP monsters and the demise of the chen conjecture. Presented at 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 52nd Annual ACM SIGACT Symposium on Theory of Computing
• Acceptance Date: Jun 9, 2020
• Online Publication Date: Jun 22, 2020
• Publication Date: 2020
• Deposit Date: Jul 10, 2020
• Publicly Available Date: Jul 14, 2020
• Pages: 91-104
• Series ISSN: 0737-8017
• Book Title: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• DOI: https://doi.org/10.1145/3357713.3384232
• Public URL: https://durham-repository.worktribe.com/output/1140982