Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups
| Název česky | Dichotomie složitostí problemů řešení systemů rovnic nad konečnými pologrupami |
|---|---|
| Autoři | |
| Rok publikování | 2007 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theory of Computing Systems |
| Fakulta / Pracoviště MU | |
| 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: |