License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.11
URN: urn:nbn:de:0030-drops-95931
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9593/
Go to the corresponding LIPIcs Volume Portal

Madelaine, Florent R. ; Martin, Barnaby

Consistency for Counting Quantifiers

pdf-format:
LIPIcs-MFCS-2018-11.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{madelaine_et_al:LIPIcs:2018:9593,
  author =	{Florent R. Madelaine and Barnaby Martin},
  title =	{{Consistency for Counting Quantifiers}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9593},
  URN =		{urn:nbn:de:0030-drops-95931},
  doi =		{10.4230/LIPIcs.MFCS.2018.11},
  annote =	{Keywords: Quantified Constraints, Constraint Satisfaction, Logic in Computer Science, Universal Algebra, Computational Complexity}
}

Keywords: Quantified Constraints, Constraint Satisfaction, Logic in Computer Science, Universal Algebra, Computational Complexity
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI