2006
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
KLÍMA, Ondřej, Benoit LAROSE a Pascal TESSONZákladní údaje
Originální název
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
Název česky
Systémy rovnic nad konečnými pologrupami a hypotéza dichotomie #CSP
Autoři
KLÍMA, Ondřej (203 Česká republika, garant), Benoit LAROSE (124 Kanada) a Pascal TESSON (124 Kanada)
Vydání
Berlin, Mathematical Foundations of Computer Science, od s. 584-595, 12 s. 2006
Nakladatel
Springer Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Slovensko
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14310/06:00017643
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-540-37791-7
ISSN
UT WoS
000240271700051
Klíčová slova anglicky
systems of equations; semigroups; #CSP problem
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 30. 3. 2010 14:08, doc. Mgr. Ondřej Klíma, Ph.D.
V originále
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.
Česky
Studujeme složitost problému určení počtu řešení systému rovnic nad pevnou konečnou pologrupou. Ukazujeme, že tento problém vždy buď náleží do třídy FP nebo je #P-úplný. Presně charkterizujeme hranici mezi těmito dvěma možnostmi. Výsledků požíváme k podpoření intuice týkající se hypotézy o dichotomii složitosti problému počítání počtu řešení v problému CSP.
Návaznosti
| MSM0021622409, záměr |
| ||
| 1M0545, projekt VaV |
|