Dmitriy Zhuk
QCSP monsters and the demise of the chen conjecture
Zhuk, Dmitriy; Martin, Barnaby
Authors
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
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
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search