Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Periodical |
| Magazine / Source | Theory of Computing Systems |
| MU Faculty or unit | |
| 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: |