Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture

Warning

This publication doesn't include Faculty of Medicine. It includes Faculty of Science. Official publication website can be found on muni.cz.

Authors	KLÍMA Ondřej LAROSE Benoit TESSON Pascal
Year of publication	2006
Type	Article in Proceedings
Conference	Mathematical Foundations of Computer Science
MU Faculty or unit	Faculty of Science
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:	Institute for Theoretical Computer Science Mathematical structures and their physical applications