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

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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:	Institut Teoretické Informatiky Matematické struktury a jejich fyzikální aplikace