The complexity of the counting constraint satisfaction problem

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book , Conference object 01 Jan 2008 English Publisher:Association for Computing Machinery (ACM)Journal:Journal of the ACM, volume 60, pages 1-41 (issn: 0004-5411, eissn: 1557-735X,

Copyright policy )

Authors: Andrei A. Bulatov;

doi: 10.1145/2528400 , 10.1007/978-3-540-70575-8_53

The complexity of the counting constraint satisfaction problem

- Summary
- Metrics

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

Related Organizations

View all View all

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	79
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%