Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bulatov, Andrei; Dalmau, Victor; Thurley, Marc http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-41955
URL:

; ;

Descriptive complexity of approximate counting CSPs

pdf-format:


Abstract

Motivated by Fagin's characterization of NP, Saluja et al. have introduced a logic based frame- work for expressing counting problems. In this setting, a counting problem (seen as a mapping C from structures to non-negative integers) is `definedí by a first-order sentence phi if for every instance A of the problem, the number of possible satisfying assignments of the variables of phi in A is equal to C(A). The logic RHPI_1 has been introduced by Dyer et al. in their study of the counting complexity class #BIS. The interest in the class #BIS stems from the fact that, it is quite plausible that the problems in #BIS are not #P-hard, nor they admit a fully polynomial randomized approximation scheme. In the present paper we investigate which counting constraint satisfaction problems #CSP(H) are definable in the monotone fragment of RHPI_1. We prove that #CSP(H) is definable in monotone RHPI_1 whenever H is invariant under meet and join operations of a distributive lattice. We prove that the converse also holds if H contains the equality relation. We also prove similar results for counting CSPs expressible by linear Datalog. The results in this case are very similar to those for monotone RHPI1, with the addition that H has, additionally, \top (the greatest element of the lattice) as a polymorphism.

BibTeX - Entry

@InProceedings{bulatov_et_al:LIPIcs:2013:4195,
  author =	{Andrei Bulatov and Victor Dalmau and Marc Thurley},
  title =	{{Descriptive complexity of approximate counting CSPs}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{149--164},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Simona Ronchi Della Rocca},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4195},
  URN =		{urn:nbn:de:0030-drops-41955},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.CSL.2013.149},
  annote =	{Keywords: Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity}
}

Keywords: Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity
Seminar: Computer Science Logic 2013 (CSL 2013)
Related Scholarly Article:
Issue date: 2013
Date of publication: 2013


DROPS-Home | Fulltext Search | Imprint Published by LZI