ECCC-Report TR07-093https://eccc.weizmann.ac.il/report/2007/093Comments and Revisions published for TR07-093en-usTue, 10 Feb 2009 00:00:00 +0200
Revision 1
| The complexity of the counting constraint satisfaction problem |
Andrei Bulatov
https://eccc.weizmann.ac.il/report/2007/093#revision1The 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.
Tue, 10 Feb 2009 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/093#revision1
Paper TR07-093
| The complexity of the counting constraint satisfaction problem |
Andrei A. Bulatov
https://eccc.weizmann.ac.il/report/2007/093The 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.
Mon, 01 Oct 2007 16:12:45 +0200https://eccc.weizmann.ac.il/report/2007/093