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
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 52nd Annual ACM SIGACT Symposium on Theory of Computing |
Acceptance Date | Jun 9, 2020 |
Online Publication Date | Jun 22, 2020 |
Publication Date | 2020 |
Deposit Date | Jul 10, 2020 |
Publicly Available Date | Jul 14, 2020 |
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
Depth lower bounds in Stabbing Planes for combinatorial principles
(2024)
Journal Article
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
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