The Complexity of the Counting Constraint Satisfaction Problem
The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite relational structure H can be expressed as follows: given a relational structure G over the same vocabulary, determine the number of homomorphisms from G to H. In this article we characterize relational structures H for which #CSP(H) can be solved in polynomial time and prove that for all other structures the problem is #P-complete.
complexity constraint satisfaction problem algorithms theory counting problems dichotomy theorem homomorphism problem