__
Revision #1 to TR07-093 | 10th February 2009 00:00
__
#### The complexity of the counting constraint satisfaction problem

**Abstract:**
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.

__
TR07-093 | 27th July 2007 00:00
__

#### The complexity of the counting constraint satisfaction problem

**Abstract:**
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.