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: | |
| Look up in GoogleScholar |
