Show simple item record

dc.contributor.authorCarvalho, Catarina
dc.contributor.authorMadelaine, Florent
dc.contributor.authorMartin, Barnaby
dc.contributor.authorZhuk, Dmitriy
dc.date.accessioned2023-04-14T11:00:02Z
dc.date.available2023-04-14T11:00:02Z
dc.date.issued2023-01-18
dc.identifier.citationCarvalho , C , Madelaine , F , Martin , B & Zhuk , D 2023 , ' The complexity of quantified constraints: Collapsibility, switchability and the algebraic formulation ' , ACM Transactions on Computational Logic (TOCL) , vol. 24 , no. 1 , pp. 1-26 . https://doi.org/10.1145/3568397
dc.identifier.issn1529-3785
dc.identifier.otherArXiv: http://arxiv.org/abs/2106.13154v1
dc.identifier.otherArXiv: http://arxiv.org/abs/2106.13154v1
dc.identifier.otherORCID: /0000-0002-4648-7016/work/133139130
dc.identifier.urihttp://hdl.handle.net/2299/26165
dc.description© 2023 Association for Computing Machinery. This is the accepted manuscript version of an article which has been published in final form at https://doi.org/10.1145/3568397
dc.description.abstractLet A be an idempotent algebra on a finite domain. By mediating between results of Chen and Zhuk, 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 is known to be false. Switchability was introduced by Chen as a generalisation of the already-known collapsibility. For three-element domain algebras A that are switchable and omit a G-set, we prove that, for every finite subset D of Inv(A), Pol(D) is collapsible. The significance of this is that, for QCSP on finite structures (over a three-element domain), all QCSP tractability (in P) explained by switchability is already explained by collapsibility.en
dc.format.extent26
dc.format.extent796533
dc.language.isoeng
dc.relation.ispartofACM Transactions on Computational Logic (TOCL)
dc.subjectcs.CC
dc.titleThe complexity of quantified constraints: Collapsibility, switchability and the algebraic formulationen
dc.contributor.institutionCentre for Computer Science and Informatics Research
dc.contributor.institutionMathematics and Theoretical Physics
dc.contributor.institutionSchool of Physics, Engineering & Computer Science
dc.contributor.institutionDepartment of Physics, Astronomy and Mathematics
dc.description.statusPeer reviewed
rioxxterms.versionofrecord10.1145/3568397
rioxxterms.typeJournal Article/Review
herts.preservation.rarelyaccessedtrue


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record