Publication details for Dr Barnaby MartinZhuk, Dmitriy & Martin, Barnaby (2020), QCSP monsters and the demise of the chen conjecture, in Makarychev, Konstantin, Makarychev, Yury, Tulsiani, Madhur, Kamath, Gautam & Chuzhoy, Julia eds, 52nd Annual ACM SIGACT Symposium on Theory of Computing. Chicago, Association for Computing Machinery, New York, 91-104.
- Publication type: Conference Paper
- ISSN/ISBN: 9781450369794 (print)
- DOI: 10.1145/3357713.3384232
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 Θ
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.