Other formats:
BibTeX
LaTeX
RIS
@inproceedings{702362, author = {Klíma, Ondřej and Larose, Benoit and Tesson, Pascal}, address = {Berlin}, booktitle = {Mathematical Foundations of Computer Science}, keywords = {systems of equations; semigroups; #CSP problem}, language = {eng}, location = {Berlin}, isbn = {978-3-540-37791-7}, pages = {584-595}, publisher = {Springer Verlag}, title = {Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture}, year = {2006} }
TY - JOUR ID - 702362 AU - Klíma, Ondřej - Larose, Benoit - Tesson, Pascal PY - 2006 TI - Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture PB - Springer Verlag CY - Berlin SN - 9783540377917 KW - systems of equations KW - semigroups KW - #CSP problem N2 - 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. ER -
KLÍMA, Ondřej, Benoit LAROSE and Pascal TESSON. Systems of Equations over Finite Semigroups and the \#{}CSP Dichotomy Conjecture. In \textit{Mathematical Foundations of Computer Science}. Berlin: Springer Verlag, 2006, p.~584-595. ISBN~978-3-540-37791-7.
|