Zhuk, Dmitriy and Martin, Barnaby (2020) 'QCSP monsters and the demise of the chen conjecture.', in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. New York: Association for Computing Machinery, pp. 91-104.
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (657Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1145/3357713.3384232 |
| Publisher statement: | © 2020 Association for Computing Machinery. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing https://doi.org/10.1145/3357713.3384232 |
| Date accepted: | 09 June 2020 |
| Date deposited: | 14 July 2020 |
| Date of first online publication: | 22 June 2020 |
| Date first made open access: | 14 July 2020 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
