Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Dichotomie složitostí problemů řešení systemů rovnic nad konečnými pologrupami
Autoři

KLÍMA Ondřej THERIEN Denis TESSON Pascal

Rok publikování 2007
Druh Článek v odborném periodiku
Časopis / Zdroj Theory of Computing Systems
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www http://www.springerlink.com/content/f60241072760q086/
Obor Obecná matematika
Klíčová slova finite semigroups; dichotomies in complexity theory; systems of equations
Popis Uvažujeme problém zda daný systém rovnic nad danou konečnou pologrupou S má řešení. V případě když S je monoid jsme ukázali, že problém lze řešit v polynomiálním čase pokud S je komutativní a je sjednocením svých podgrup, ale problém je NP=úplným jinak. V případě že S je monoid či regulární pologrupa, jsme dokázali podobnou dichotomii pro modifikovaný problém, kdy se proměnné vyskytují pouze na jedné straně rovnic. Studovali jsme též vztahy mezi těmito našimy problémy a tzv. CSP problémem. Přesněji, pro libovolnou množinu D a konečnou množinu relací T na D, jsme zkonstruovali pologrupu S(T) takovou, že problém CSP(T) je polynomiálně ekvivalentní problému řešení rovnic nad S(T).
Související projekty:

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