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