Bulatov, Andrei ;
Dalmau, Victor ;
Thurley, Marc
Descriptive complexity of approximate counting CSPs
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 nonnegative integers) is `defined’ by a firstorder 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 #Phard, 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 = {149164},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897606},
ISSN = {18688969},
year = {2013},
volume = {23},
editor = {Simona Ronchi Della Rocca},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4195},
URN = {urn:nbn:de:0030drops41955},
doi = {10.4230/LIPIcs.CSL.2013.149},
annote = {Keywords: Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity}
}
2013
Keywords: 

Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity 
Seminar: 

Computer Science Logic 2013 (CSL 2013)

Issue date: 

2013 
Date of publication: 

2013 