Publication details for Dr Barnaby MartinMadelaine, Florent & Martin, Barnaby (2018), Consistency for counting quantifiers, in Potapov, Igor, Spirakis, Paul & Worrell, James eds, Leibniz International Proceedings in Informatics (LIPIcs) 117: 43rd International Symposium on Mathematical Foundations of Computer Science. Liverpool, UK, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 11:1--11:13.
- Publication type: Conference Paper
- ISSN/ISBN: 1868-8969, 9783959770866
- DOI: 10.4230/LIPIcs.MFCS.2018.11
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.