Theory of Computing
-------------------
Title : The Cayley Semigroup Membership Problem
Authors : Lukas Fleischer
Volume : 18
Number : 8
Pages : 1-18
URL : https://theoryofcomputing.org/articles/v018a008
Abstract
--------
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 Szemeredi 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--Hastad 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).