Volume 18 (2022) Article 8 pp. 1-18
CCC 2018 Special Issue

The Cayley Semigroup Membership Problem

by Lukas Fleischer

Received: June 28, 2018
Revised: July 25, 2021
Published: April 25, 2022

$ \newcommand{\ensuremath}[1]{#1} \newcommand{\FOLL}{\ensuremath{\mathsf{FOLL}}} \newcommand{\AC}{\ensuremath{\mathsf{AC}}} \newcommand{\qAC}{\ensuremath{\mathsf{qAC}}} \newcommand{\LOGSPACE}{\ensuremath{\mathsf{Logspace}}} \newcommand{\NL}{\ensuremath{\mathsf{NL}}} \newcommand{\Parity}{\ensuremath{\textsc{Parity}}} \newcommand{\SCSM}{Cayley semigroup membership} \newcommand{\SCSMP}{{\SCSM} problem} \newcommand{\Hastad}{H{\aa}stad} $

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).

DOI: 10.4086/toc.2022.v018a008

© 2022 Lukas Fleischer
Licensed under a Creative Commons Attribution License (CC-BY)