Skip to main content

Research Repository

Advanced Search

QCSP monsters and the demise of the chen conjecture

Zhuk, Dmitriy; Martin, Barnaby

QCSP monsters and the demise of the chen conjecture Thumbnail


Authors

Dmitriy Zhuk



Contributors

Konstantin Makarychev
Editor

Yury Makarychev
Editor

Madhur Tulsiani
Editor

Gautam Kamath
Editor

Julia Chuzhoy
Editor

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). QCSP monsters and the demise of the chen conjecture. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (91-104). https://doi.org/10.1145/3357713.3384232

Conference Name 52nd Annual ACM SIGACT Symposium on Theory of Computing
Conference Location Chicago
Acceptance Date Jun 9, 2020
Online Publication Date Jun 22, 2020
Publication Date 2020
Deposit Date Jul 10, 2020
Publicly Available Date Mar 29, 2024
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

Files

Accepted Conference Proceeding (672 Kb)
PDF

Copyright 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





You might also like



Downloadable Citations