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

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	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:	Institut Teoretické Informatiky