On the Complexity of the Cayley Semigroup Membership Problem

Lukas Fleischer

We investigate the complexity of deciding, given a multiplication table representing a semigroup S, a subset X of S and an element t of S, whether t can be expressed as a product o…