Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details for Dr Barnaby Martin

Zhuk, 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.

Author(s) from Durham

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.