Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DICHOTOMY RESULTS:
Reports tagged with dichotomy results:
TR04-091 | 29th September 2004
Ondrej Klíma, Pascal Tesson, Denis Thérien

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

We consider the problem of testing whether a given system of equations
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 subgroups
more >>>




ISSN 1433-8092 | Imprint