Publication details
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Proceedings |
| Conference | Mathematical Foundations of Computer Science |
| MU Faculty or unit | |
| Citation | |
| Field | General mathematics |
| Keywords | systems of equations; semigroups; #CSP problem |
| Description | We study the complexity of counting the number of solutions to a system of equations over a fixed finite semigroup. We show that this problem is always either in FP or #P-complete and describe the borderline precisely. We use these results to convey some intuition about the conjectured dichotomy for the complexity of counting the number of solutions in constraint satisfaction problems. |
| Related projects: |