License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.261
URN: urn:nbn:de:0030-drops-30161
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3016/
Dyer, Martin ;
Richerby, David
The #CSP Dichotomy is Decidable
Abstract
Bulatov (2008) and Dyer and Richerby (2010) have established the following dichotomy for the counting constraint satisfaction problem (#CSP): for any constraint language Gamma, the
problem of computing the number of satisfying assignments to constraints drawn from Gamma is either in FP or is #P-complete, depending on the structure of Gamma. The principal question left open by this research was whether the criterion of the dichotomy is decidable. We show that it is; in fact, it is in NP.
BibTeX - Entry
@InProceedings{dyer_et_al:LIPIcs:2011:3016,
author = {Martin Dyer and David Richerby},
title = {{The #CSP Dichotomy is Decidable}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {261--272},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-25-5},
ISSN = {1868-8969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3016},
URN = {urn:nbn:de:0030-drops-30161},
doi = {10.4230/LIPIcs.STACS.2011.261},
annote = {Keywords: constraint satisfaction problem, counting problems, complexity dichotomy, decidability}
}
|
Keywords: |
|
constraint satisfaction problem, counting problems, complexity dichotomy, decidability |
|
Collection: |
|
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
11.03.2011 |
