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

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KLÍMA Ondřej THERIEN Denis TESSON Pascal

Year of publication 2007
Type Article in Periodical
Magazine / Source Theory of Computing Systems
MU Faculty or unit

Faculty of Science

Citation
Web http://www.springerlink.com/content/f60241072760q086/
Field General mathematics
Keywords finite semigroups; dichotomies in complexity theory; systems of equations
Description 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).
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.