Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Consistency for counting quantifiers.

Madelaine, Florent and Martin, Barnaby (2018) 'Consistency for counting quantifiers.', in 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 11:1-11:13. Leibniz International Proceedings in Informatics (LIPIcs)., 117

Abstract

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.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(455Kb)
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
(546Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.4230/LIPIcs.MFCS.2018.11
Publisher statement:© B. Martin and F. R. Madelaine; licensed under Creative Commons License CC-BY
Date accepted:13 June 2018
Date deposited:13 July 2018
Date of first online publication:2018
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar