Informace o publikaci
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 | |
| Rok publikování | 2006 |
| Druh | Článek ve sborníku |
| Konference | Mathematical Foundations of Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | KLÍMA, Ondřej, Benoit LAROSE a Pascal TESSON. Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture. In Mathematical Foundations of Computer Science. Berlin: Springer Verlag, 2006, s. 584-595. ISBN 978-3-540-37791-7. |
| Obor | Obecná matematika |
| Klíčová slova | systems of equations; semigroups; #CSP problem |
| Popis | 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. |
| Související projekty: |