The Complexity of the Counting Constraint Satisfaction Problem
Andreǐ A. Bulatov · Lecture notes in computer science · 2008
The Counting Constraint Satisfaction Problem ( ${\rm \#CSP}(\mathcal{H})$ ) over a finite relational structure $\mathcal{H}$ can be expressed as follows: given a relational structure $\mathcal{G}$ over the same vocabulary, determine the number of homomorphisms from $\mathcal{G}$ to $\mathcal{H}$ . In this paper we characterize relational structures $\mathcal{H}$ for which ${\rm \#CSP}(\mathcal{H})$ can be solved in polynomial time and prove that for all other structures the problem is #P-complete.