2007
Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups
KLÍMA, Ondřej; Denis THERIEN a Pascal TESSONZá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
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
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
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 1. 2. 2010 10:35, doc. Mgr. Ondřej Klíma, Ph.D.
V originále
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).
Č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 VaV |
|