We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

QCSP monsters and the demise of the chen conjecture.

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.


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
Publisher Web site:
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
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

Look up in GoogleScholar