Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-093 | 10th February 2009 00:00

The complexity of the counting constraint satisfaction problem

RSS-Feed




Revision #1
Authors: Andrei Bulatov
Accepted on: 10th February 2009 00:00
Downloads: 1663
Keywords: 


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.


Paper:

TR07-093 | 27th July 2007 00:00

The complexity of the counting constraint satisfaction problem





TR07-093
Authors: Andrei A. Bulatov
Publication: 1st October 2007 16:12
Downloads: 1301
Keywords: 


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.



ISSN 1433-8092 | Imprint