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

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Systémy rovnic nad konečnými pologrupami a hypotéza dichotomie #CSP
Autoři

KLÍMA Ondřej LAROSE Benoit TESSON Pascal

Rok publikování 2006
Druh Článek ve sborníku
Konference Mathematical Foundations of Computer Science
Fakulta / Pracoviště MU

Přírodovědecká fakulta

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.