KLÍMA, Ondřej, Denis THERIEN a Pascal TESSON. Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups. Theory of Computing Systems, New York: Springer, 2007, roč. 40, č. 3, s. 263-297. ISSN 1432-4350.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název 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 KLÍMA, Ondřej (203 Česká republika, garant), Denis THERIEN (124 Kanada) a Pascal TESSON (124 Kanada).
Vydání Theory of Computing Systems, New York, Springer, 2007, 1432-4350.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Pure mathematics
Stát vydavatele Spojené státy americké
Utajení není předmětem státního či obchodního tajemství
WWW URL
Impakt faktor Impact factor: 0.625
Kód RIV RIV/00216224:14310/07:00022898
Organizační jednotka Přírodovědecká fakulta
UT WoS 000243880000004
Klíčová slova anglicky finite semigroups; dichotomies in complexity theory; systems of equations
Štítky dichotomies in complexity theory, finite semigroups, systems of equations
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Změněno: 1. 2. 2010 10:35.
Anotace
We consider the problem of testing whether a given system of equation over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgoups but is NP-complete otherwise. When S is a monoid ar regular semigroup, we obtain similar dichotomies for the restricted version of the problem where no variable occurs on the right-hand side of each equation. We stress conections between these problems and constraint satisfaction problems. In particular, for any finite domain D and any finite set of relations T over D, we construct a finite semigroup S(T) such that CSP(T) is polynomial-time equivalent to the equation satisfiability problem over S(T).
Anotace česky
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).
Návaznosti
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 21. 8. 2019 03:03