2026-07-21T03:11:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9593 2024-03-06T10:44:29Z ddc:004 open_access

Consistency for Counting Quantifiers Madelaine, Florent R. Martin, Barnaby Quantified Constraints Constraint Satisfaction Logic in Computer Science Universal Algebra Computational Complexity We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all unary relations. For each such structure, either the corresponding CSP with counting quantifiers is in P, or it is NP-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florent R. Madelaine and Barnaby Martin 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.11 urn:nbn:de:0030-drops-95931 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode