Revised: July 25, 2021

Published: April 25, 2022

**Keywords:**subsemigroup, multiplication table, generators, completeness, quasi-polynomial-size circuits, FOLL

**Categories:**complexity theory, semigroups, completeness, circuit complexity, quasipolynomial, CCC, CCC 2018 special issue, short

**ACM Classification:**F.2.2, F.4.3

**AMS Classification:**20M35, 68Q17, 68Q25, 68Q45, 68Q70

**Abstract:**
[Plain Text Version]

The *Cayley semigroup membership problem* asks, 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 of elements of $X$.
It is well-known that this problem is $\NL$-complete
under $\AC^0$-reductions.
For groups, the problem can be solved in deterministic
$\LOGSPACE$.
This raised the question of determining the exact complexity of this variant.
Barrington, Kadau, Lange and McKenzie showed that for Abelian groups and for
certain solvable groups, the problem is contained in the complexity class
$\FOLL$
(polynomial-size, $O(\log\log n)$-depth circuits)
and they concluded that these variants are not hard,
under $\AC^0$ reductions,
for any complexity class containing the Parity language. The more
general case of arbitrary groups remained open.
In this
article,
we apply results by Babai and Szemerédi directly to this
setting to show that the problem is solvable in $\qAC^0$ (quasi-polynomial
size circuits of constant depth with unbounded fan-in). We prove a similar
result for commutative semigroups. Combined with the Yao--Håstad
circuit lower bound,
it follows immediately that Cayley semigroup membership for groups and
Cayley semigroup membership for commutative semigroups are not hard,
under $\AC^0$ reductions, for any class containing Parity.
Moreover, we prove that $\NL$-completeness already holds for the classes
of $0$-simple semigroups and nilpotent semigroups.
Together with our results on groups and commutative semigroups, we prove the
existence of a natural class of finite semigroups that generates a variety of
finite semigroups with $\NL$-complete Cayley semigroup membership,
while the Cayley semigroup membership problem for the
class itself is not $\NL$-hard.
We also discuss applications of our technique to $\FOLL$ and describe
varieties for which the Cayley semigroup membership problem
is in $\AC^0$.

-------------------

A preliminary version of this paper appeared in the Proceedings of the 33rd Computational Complexity Conference (CCC'18).