Consistency for counting quantifiers

Madelaine, Florent; Martin, Barnaby

doi:10.4230/lipics.mfcs.2018.11

Consistency for counting quantifiers

Madelaine, Florent; Martin, Barnaby

Authors

Florent Madelaine

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Contributors

Igor Potapov
Editor

Paul Spirakis
Editor

James Worrell
Editor

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.

Citation

Madelaine, F., & Martin, B. (2018). Consistency for counting quantifiers. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (11:1-11:13). https://doi.org/10.4230/lipics.mfcs.2018.11

Conference Name	43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
Conference Location	Liverpool, UK
Start Date	Aug 27, 2018
End Date	Aug 31, 2018
Acceptance Date	Jun 13, 2018
Publication Date	Aug 31, 2018
Deposit Date	Jul 12, 2018
Publicly Available Date	Jun 27, 2019
Volume	117
Pages	11:1-11:13
Series Title	Leibniz International Proceedings in Informatics (LIPIcs)
Series ISSN	1868-8969
Book Title	43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK).
DOI	https://doi.org/10.4230/lipics.mfcs.2018.11
Public URL	https://durham-repository.worktribe.com/output/1145134