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