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

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F06%3A00017643" target="_blank" >RIV/00216224:14310/06:00017643 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
Popis výsledku v původním jazyce
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 someintuition about the conjectured dichotomy for the complexity of counting the number of solutions in constraint satisfaction problems.
Název v anglickém jazyce
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
Popis výsledku anglicky
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 someintuition about the conjectured dichotomy for the complexity of counting the number of solutions in constraint satisfaction problems.

Projekt
<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2006
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)