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

Warning

This publication doesn't include Faculty of Arts. 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:

You are running an old browser version. We recommend updating your browser to its latest version.