Catarina Carvalho
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby; Zhuk, Dmitriy
Authors
Abstract
Let A be an idempotent algebra on a finite domain. By mediating between results of Chen [1] and Zhuk [2], we argue that if A satisfies the polynomially generated powers property (PGP) and B is a constraint language invariant under A (that is, in Inv(A)), then QCSP(B) is in NP. In doing this we study the special forms of PGP, switchability and collapsibility, in detail, both algebraically and logically, addressing various questions such as decidability on the way. We then prove a complexity-theoretic converse in the case of infinite constraint languages encoded in propositional logic, that if Inv(A) satisfies the exponentially generated powers property (EGP), then QCSP(Inv(A)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying what we term the Revised Chen Conjecture. This result becomes more significant now the original Chen Conjecture (see [3]) is known to be false [4]. Switchability was introduced by Chen in [1] as a generalisation of the already-known collapsibility [5]. There, an algebra A := ({0, 1, 2}; 𝑟 ) was given that is switchable and not collapsible. We prove that, for all finite subsets Δ of Inv(A), Pol(Δ) is collapsible. The significance of this is that, for QCSP on finite structures, it is still possible all QCSP tractability (in NP) explained by switchability is already explained by collapsibility. At least, no counterexample is known to this.
Citation
Carvalho, C., Madelaine, F., Martin, B., & Zhuk, D. (2023). The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Transactions on Computational Logic, 24(1), Article 5. https://doi.org/10.1145/3568397
Journal Article Type | Article |
---|---|
Acceptance Date | Jun 24, 2022 |
Online Publication Date | Oct 17, 2022 |
Publication Date | 2023-01 |
Deposit Date | Jul 16, 2022 |
Publicly Available Date | Jul 18, 2022 |
Journal | ACM Transactions on Computational Logic |
Print ISSN | 1529-3785 |
Electronic ISSN | 1557-945X |
Publisher | Association for Computing Machinery (ACM) |
Peer Reviewed | Peer Reviewed |
Volume | 24 |
Issue | 1 |
Article Number | 5 |
DOI | https://doi.org/10.1145/3568397 |
Files
Accepted Journal Article
(891 Kb)
PDF
Copyright Statement
© 2022 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 ACM Transactions on Computational Logic, https://doi.org/10.1145/3568397
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
Surjective H-colouring: New hardness results
(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