文章基本信息

标题：The #CSP Dichotomy is Decidable
本地全文：下载
作者：Martin Dyer ; David Richerby
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：261-272
DOI：10.4230/LIPIcs.STACS.2011.261
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：constraint satisfaction problem; counting problems; complexity dichotomy; decidability