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 paper 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.

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 paper 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.