The #CSP Dichotomy is Decidable

Martin Dyer & David Richerby
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,...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.