The Cayley Semigroup Membership Problem

Authors Lukas Fleischer,

Plaintext

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18
www.theoryofcomputing.org

S PECIAL ISSUE : CCC 2018

The Cayley Semigroup Membership
Problem
Lukas Fleischer∗
Received June 28, 2018; Revised July 25, 2021; Published April 25, 2022

Abstract
The Cayley semigroup membership problem asks, given a multiplication table representing a
semigroup 𝑆, a subset 𝑋 of 𝑆 and an element 𝑡 of 𝑆, whether 𝑡 can be expressed as a product
of elements of 𝑋. It is well-known that this problem is NL-complete under AC0 -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, 𝑂(log log 𝑛)-depth circuits) and they concluded
that these variants are not hard, under AC0 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 qAC0 (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 AC0

A preliminary version of this paper appeared in the Proceedings of the 33rd Computational Complexity
Conference (CCC’18) [17].
∗ This work was supported by the DFG grant DI 435/5–2.

ACM Classification: F.2.2, F.4.3
AMS Classification: 20M35, 68Q17, 68Q25, 68Q45, 68Q70
Key words and phrases: subsemigroup, multiplication table, generators, completeness, quasi-
polynomial-size circuits, FOLL

© 2022 Lukas Fleischer
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a008
L UKAS F LEISCHER

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

1 Introduction
Back in 1976, Jones and Laaser studied the complexity of the generation problem which is formally
defined as follows.

GEN
Input: A set 𝐺, a binary operation ◦ : 𝐺 × 𝐺 → 𝐺, a set 𝑋 ⊆ 𝐺 and an element 𝑡 ∈ 𝐺
Question: Is 𝑡 contained in the smallest superset of 𝑋 closed under ◦?

They showed that this problem is P-complete1 [21], an observation which has since been
used in many other P-completeness results. Barrington and McKenzie later studied natural
subproblems and connected them to standard subclasses of P [8]. Following [10], the generation
problem is also referred to as Cayley groupoid membership problem. This terminology stems from
the fact that the set 𝐺 forms a groupoid when equipped with the operation ◦ and the objective
is to decide whether 𝑡 belongs to the subgroupoid generated by 𝑋. The prefix Cayley is due to
the representation of finite groupoid by its multiplication table, often also called Cayley table.
It is not surprising that imposing further structural properties on the multiplication table
affects the complexity of the Cayley groupoid membership problem. For example, if the
multiplication table is required to be associative, one obtains the associative generation problem,
henceforth referred to as Cayley semigroup membership problem. This decision problem is NL-
complete [22]. We will analyze its complexity when further restricting the semigroups encoded
by the input. For a class of finite semigroups C, the Cayley semigroup membership problem for C is
defined as follows.

CSM(C)
Input: The Cayley table of a semigroup 𝑆 ∈ C, a set 𝑋 ⊆ 𝑆 and an element 𝑡 ∈ 𝑆
Question: Is 𝑡 in the subsemigroup of 𝑆 generated by 𝑋?

The motivation for investigating this problem is two-fold. First, there is a direct connection
between the Cayley semigroup membership problem and decision problems for regular
languages: a language 𝐿 ⊆ Σ+ is regular if and only if there exist a finite semigroup 𝑆, a
morphism 𝜑 : Σ+ → 𝑆 and a set 𝑃 ⊆ 𝑆 such that 𝐿 = 𝜑 −1 (𝑃). Thus, morphisms to finite

1In this paper, all completeness/hardness statements are with respect to AC0 reductions. Even though some
of the cited articles only claim completeness under Logspace or NC1 reductions, their reductions can in fact be
implemented in AC0 .

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 2
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

semigroups can be seen as a way of encoding regular languages. For encoding such a semigroup,
specifying the multiplication table is a natural choice. Deciding emptiness of a regular language
represented by a morphism 𝜑 : Σ+ → 𝑆 to a finite semigroup 𝑆 and a set 𝑃 ⊆ 𝑆 boils down
to checking whether any of the elements from the set 𝑃 is contained in the subsemigroup
of 𝑆 generated by the images of the letters of Σ under 𝜑. Conversely, the Cayley semigroup
membership problem is a special case of the emptiness problem for regular languages: an
element 𝑡 ∈ 𝑆 is contained in the subsemigroup generated by a set 𝑋 ⊆ 𝑆 if and only if the
language 𝜑−1 (𝑃) with 𝜑 : 𝑋 + → 𝑆, 𝑥 ↦→ 𝑥 and 𝑃 = {𝑡} is non-empty.
Second, we hope to get a better understanding of the connection between algebra and
low-level complexity classes included in NL in a fashion similar to the results of [8]. In the past,
several intriguing links between so-called varieties of finite semigroups and the computational
complexity of algebraic problems for such varieties were made. For example, the word problem
for a fixed finite semigroup was shown to be in AC0 if the semigroup is aperiodic, in ACC0 if the
semigroup is solvable and NC1 -complete otherwise [7, 9].

Related work. The first completeness results for the Cayley groupoid membership problem
appeared in work by Jones and Laaser [21], and completeness results on the Cayley semigroup
membership problem appeared in a paper by Jones, Lien and Laaser [22].
The semigroup membership problem and its restrictions to varieties of finite semigroups
was also studied for other encodings of the input, such as matrix semigroups [2, 6, 4] or
transformation semigroups [27, 18, 5, 12, 14, 13, 11]. In [6], Babai and Szemerédi introduced
the Black Box Group model, and applied it to matrix groups over finite fields. The Black Box
Group model also has direct applications in the Cayley table model — however, to the best of
our knowledge, this connection has not been investigated prior to the present paper.
Further systematic study of the group membership problem in the Cayley model (CSM(G),
using our notation) began with a paper by Barrington and McKenzie in 1991 [8]. They observed
that the problem is in SymmetricLogspace which has been shown by Reingold in 2008 [26] to be
the same as deterministic Logspace, and they suggested it might be complete for deterministic
Logspace. However, all attempts to obtain a hardness proof failed (in fact, the conjecture is
shown to be false in this paper). There was no progress in a long time until Barrington, Kadau,
Lange and McKenzie showed in 2001 [10] that for Abelian groups and certain solvable groups,
the problem lies in the complexity class FOLL (decidable by circuits of polynomial size and
𝑂(log log 𝑛) depth) and thus cannot be hard for any complexity class containing Parity.
The case of arbitrary finite groups remained open partly due to the lack of awareness of the
relevance of the early work by Babai and Szemerédi [6]. With this paper we are closing this
information gap. We give more details of the connection in Section 4.

Our contributions. We show that the Cayley semigroup membership problem for the
variety G of finite groups and the variety Com of commutative semigroups are contained in
qAC0 and thus cannot be hard for any class containing Parity. Our approach heavily relies on
the application of techniques from [6] to the Cayley table setting. The key observation is that
every element of a group 𝐺 (or commutative semigroup 𝑆) can be computed by an algebraic

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 3
L UKAS F LEISCHER

circuit of size 𝒪(log3 |𝐺|) (size 𝒪(log2 |𝑆|), resp.) over any set of generators.
By means of a closer analysis of the technique used by Jones, Lien and Laaser in [22], we also
show that the Cayley semigroup membership problem remains NL-complete when restricting
the input to 0-simple semigroups or to nilpotent semigroups.
Combining our results, we obtain that the Cayley semigroup membership problem for
the class G ∪ Com is decidable in qAC0 (and thus not NL-hard) while the Cayley semigroup
membership problem for the minimal variety of finite semigroups containing G ∪ Com is
NL-complete.
We discuss the extent to which our approach can be used to establish membership of Cayley
semigroup membership variants in the complexity class FOLL. Here, we use an idea based on
repeated squaring. This technique generalizes some of the main concepts used in [10]. Finally,
we give examples of varieties for which the Cayley semigroup membership problem is in AC0 .

2 Preliminaries
Algebra. A semigroup 𝑇 is a subsemigroup of 𝑆 if 𝑇 is a subset of 𝑆 closed under multiplica-
tion. The direct product of two semigroups 𝑆 and 𝑇 is the Cartesian product 𝑆 × 𝑇 equipped with
componentwise multiplication. A semigroup 𝑇 is a quotient of a semigroup 𝑆 if there exists a
surjective morphism 𝜑 : 𝑆 → 𝑇. A semigroup 𝑇 divides a semigroup 𝑆 if there exists a surjective
morphism from a subsemigroup of 𝑆 onto 𝑇.
For every element 𝑠 of a finite semigroup 𝑆, there exist natural numbers 𝑖, 𝑝 > 0 such that
𝑠 𝑖+𝑝 = 𝑠 𝑖 . This implies 𝑠 𝑗+𝑝 = 𝑠 𝑗 for all 𝑗 ⩾ 𝑖. In particular, we have (𝑠 𝑖𝑝 )2 = 𝑠 𝑖𝑝+𝑖𝑝 = 𝑠 𝑖𝑝 , which
shows that in a finite semigroup, every element has an idempotent power. An element 𝑧 ∈ 𝑆 is a
zero element if 𝑠𝑧 = 𝑧 = 𝑧𝑠 for all 𝑠 ∈ 𝑆. It is easy to see that every semigroup contains at most
one zero element. It is usually denoted by 0.
A variety of finite semigroups is a class of finite semigroups that is closed under finite direct
products and under taking divisors. Since we are only interested in finite semigroups, we will
henceforth use the term variety for a variety of finite semigroups. Note that in the literature, such
classes of semigroups are often called pseudovarieties, as opposed to Birkhoff varieties which are
also closed under infinite direct products. The following varieties play an important role in this
paper:

• Ab, the class of all finite Abelian groups,

• Com, the class of all finite commutative semigroups,

• G, the class of all finite groups,

• N, the class of all finite nilpotent semigroups, i. e., finite semigroups 𝑆 with a zero element 0
such that for all 𝑠 ∈ 𝑆, there exists an integer 𝑒 ∈ ℕ with 𝑠 𝑒 = 0,

• LI, the class of all finite locally trivial semigroups, i. e., finite semigroups 𝑆 where 𝑒 𝑠𝑒 = 𝑒
for all elements 𝑠 ∈ 𝑆 and all idempotent elements 𝑒 ∈ 𝑆,

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 4
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

• LI 𝑘 , the class of all finite semigroups 𝑆 that satisfy 𝑥 1 · · · 𝑥 𝑘 𝑧 𝑦 𝑘 · · · 𝑦1 = 𝑥 1 · · · 𝑥 𝑘 𝑦 𝑘 · · · 𝑦1 for
all 𝑥 1 , . . . , 𝑥 𝑘 , 𝑦1 , . . . , 𝑦 𝑘 , 𝑧 ∈ 𝑆.

Note that by definition, the only idempotent element of a nilpotent semigroup is the zero
element. For finite semigroups, having exactly one idempotent element which is a zero element
actually characterizes nilpotency: for a finite semigroup 𝑆 with this property and an element
𝑠 ∈ 𝑆, choosing 𝑒 ∈ ℕ such that 𝑠 𝑒 is idempotent, we obtain 𝑠 𝑒 = 0. From this observation, it
follows immediately that every finite nilpotent semigroup is locally trivial, i. e., N ⊆ LI.
It is easy to verify that every semigroup in LI 𝑘 is locally trivial. Moreover, if 𝑆 is a finite
locally trivial semigroup, then 𝑆 belongs to LI|𝑆| . Therefore, LI = 𝑘∈ℕ LI 𝑘 . The classes LI 𝑘
Ð
form an infinite strict hierarchy within LI.
The join of two varieties V and W, denoted by V ∨ W, is the smallest variety containing both
V and W. A semigroup 𝑆 is 0-simple if it contains a zero element 0 and if for each 𝑠 ∈ 𝑆 \ {0},
one has 𝑆𝑠𝑆 = 𝑆. The class of finite 0-simple semigroups does not form a variety.
For a comprehensive introduction to the algebraic concepts used in this paper, we refer to
the textbooks [20] and [25].

Complexity. We assume familiarity with standard definitions from circuit complexity; see,
e. g., [28] for an introduction. We consider unbounded fan-in Boolean circuits which consist of
unbounded fan-in AND gates, unbounded fan-in OR gates and fan-in-1 NOT gates. The size of
such a circuit is the total number of AND and OR gates. The length of a path in the circuit is the
total number of AND and OR gates occurring on the path. The length of the longest path from
an input gate to the output gate is the depth of the circuit. Note that NOT gates are not counted
when measuring the size or depth of a circuit. A function has quasi-polynomial growth if it is
𝑐
contained in 2𝒪(log 𝑛) for some fixed 𝑐 ∈ ℕ .
Throughout the paper, we will consider the following unbounded fan-in Boolean circuit
families:

• AC0 , languages decidable by circuit families of depth 𝒪(1) and polynomial size,

• qAC0 , languages decidable by circuit families of depth 𝒪(1) and quasi-polynomial size,

• FOLL, languages decidable by circuit families of depth 𝒪(log log 𝑛) and polynomial size,

• AC1 , languages decidable by circuit families of depth 𝒪(log 𝑛) and polynomial size,

• P/poly, languages decidable by circuit families of polynomial size (and unbounded depth).

We will also briefly refer to the complexity classes ACC0 , TC0 , NC1 , Logspace and NL. It
is known that the Parity function cannot be computed by AC0 , FOLL or qAC0 circuits. This
follows directly from Håstad’s and Yao’s famous lower bound results [19, 29], which state that
the number of Boolean gates required for a depth-𝑑 circuit to compute Parity is exponential in
𝑛 1/(𝑑−1) .

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 5
L UKAS F LEISCHER

Remark 2.1. We use AC0 , ACC0 , TC0 , NC1 , AC1 , qAC0 , FOLL to refer to the non-uniform variants
of these complexity classes, even though the same identifiers are sometimes also used to refer
to uniform variants in related work. While our proofs also work in the uniform setting, our
main results do not require uniformity. Proving that our algorithms can also be implemented as
uniform circuits requires introducing the non-standard notion of DPOLYLOGTIME-uniformity
and some caution in the proofs. To avoid additional technical details and to keep the proofs
short and self-contained, we refrain from doing so.

3 Hardness results
Before looking at parallel algorithms for the Cayley semigroup membership problem, we
establish two new NL-hardness results. To this end, we first analyze the construction already
used by Jones, Lien and Laaser [22]. It turns out that the semigroups used in their reductions
are 0-simple which leads to the following result.
Theorem 3.1. For a class containing all 0-simple semigroups, the Cayley semigroup membership problem
is NL-complete (under AC0 many-one reductions).
Proof. To keep the proof self-contained, we briefly describe the reduction from the connectivity
problem for directed graphs (henceforth called STConn) to the Cayley semigroup membership
problem given in [22].
Let 𝐺 = (𝑉 , 𝐸) be a directed graph. We construct a semigroup on the set 𝑆 = 𝑉 × 𝑉 ∪ {0}
where 0 is a zero element and the multiplication rule for the remaining elements is
(
(𝑣, 𝑦) if 𝑤 = 𝑥,
(𝑣, 𝑤) · (𝑥, 𝑦) =
0 otherwise.

By construction, the subsemigroup of 𝑆 generated by 𝐸 ∪ {(𝑣, 𝑣) | 𝑣 ∈ 𝑉 } contains an element
(𝑠, 𝑡) if and only if 𝑡 is reachable from 𝑠 in 𝐺. To see that the semigroup 𝑆 is 0-simple, note that for
pairs of arbitrary elements (𝑣, 𝑤) ∈ 𝑉 × 𝑉 and (𝑥, 𝑦) ∈ 𝑉 × 𝑉, one has (𝑥, 𝑣)(𝑣, 𝑤)(𝑤, 𝑦) = (𝑥, 𝑦),
which implies 𝑆(𝑣, 𝑤)𝑆 = 𝑆.
In order to prove NL-completeness for another common class of semigroups, we use a
construction reminiscent of the “layer technique”, which is usually used to show that STConn
remains NL-complete when the inputs are acyclic graphs.
Theorem 3.2. CSM(N) is NL-complete (under AC0 many-one reductions).
Proof. Following the proof of Theorem 3.1, we describe an AC0 reduction of STConn to CSM(N).
Let 𝐺 = (𝑉 , 𝐸) be a directed graph with 𝑛 vertices. We construct a semigroup on the set
𝑆 = 𝑉 × {1, . . . , 𝑛 − 1} × 𝑉 ∪ {0} where 0 is a zero element and the multiplication rule for the
remaining elements is
(
(𝑣, 𝑖 + 𝑗, 𝑦) if 𝑤 = 𝑥 and 𝑖 + 𝑗 < 𝑛,
(𝑣, 𝑖, 𝑤) · (𝑥, 𝑗, 𝑦) =
0 otherwise.

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 6
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

The subsemigroup of 𝑆 generated by the set {(𝑣, 1, 𝑤) | 𝑣 = 𝑤 or (𝑣, 𝑤) ∈ 𝐸} contains the element
(𝑠, 𝑛 − 1, 𝑡) if and only if 𝑡 is reachable (in less than 𝑛 steps) from 𝑠 in 𝐺. Clearly, the zero element
is the only idempotent in 𝑆, so 𝑆 is nilpotent. Also, it is readily verified that the reduction can be
performed by an AC0 circuit family.

4 Parallel algorithms for Cayley semigroup membership
In the Black Box Group model introduced by Babai and Szemerédi [6], group elements are
encoded by bit strings of uniform length, and group operations (computing products and inverse
elements2) are performed by an oracle. Babai and Szemerédi showed that subgroup membership
is in NP relative to the group oracle. Together with the following observations, it follows
that in the Cayley table setting, subgroup membership can be decided in non-deterministic
polylogarithmic time in the random-access Turing machine model:

• Without loss of generality, we can assume that there are only logarithmically many
generators in the input, since a generating subset of this size can be guessed in non-
deterministic polylogarithmic time.

• A single oracle query can be simulated in non-deterministic logarithmic time (non-
determinism is only required to compute the inverse of an element).

Since qAC0 contains all languages decidable in non-deterministic polylogarithmic time, it follows
that CSM(G) is in qAC0 .
In the remainder of this section, we will give a more self-contained proof of this result,
and expand it to other classes of semigroups. We will use algebraic circuits as a succinct
representation of elements in an algebraic structure, similarly to the approach taken in [6].
Unlike in usual algebraic circuits, in the context of the Cayley semigroup membership problem,
the algebraic structure is not fixed but given as part of the input. We will introduce so-called
Cayley circuits to deal with this setting. Since these circuits will be used for the Cayley semigroup
membership problem only, we confine ourselves to cases where the algebraic structure is a finite
semigroup.

4.1 Cayley circuits
A Cayley circuit is a directed acyclic graph with topologically ordered vertices such that each
vertex has in-degree 0 or 2. In the following, to avoid technical subtleties when squaring an
element, we allow multi-edges. The vertices of a Cayley circuit are called gates. The vertices
with in-degree 0 are called input gates and vertices with in-degree 2 are called product gates. Each
Cayley circuit also has a designated gate of out-degree 0, called the output gate. For simplicity,
we assume that the output gate always corresponds to the maximal gate with regard to the
2Babai and Szemerédi [6] consider the more general model where multiple strings may encode the same group
element; in this case, an oracle to recognize the identity element needs to be added. However, in the present paper
we only consider the case of unique encoding.

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 7
L UKAS F LEISCHER

vertex order. The size of a Cayley circuit 𝒞, denoted by |𝒞|, is the number of gates of 𝒞. An input
to a Cayley circuit 𝒞 with 𝑘 input gates consists of a finite semigroup 𝑆 and elements 𝑥 1 , . . . , 𝑥 𝑘
of 𝑆. Given such an input, the value of the 𝑖-th input gate is 𝑥 𝑖 and the value of a product gate,
whose predecessors have values 𝑥 and 𝑦, is the product 𝑥 · 𝑦 in 𝑆. The value of the circuit 𝒞 is the
value of its output gate. We will denote the value of 𝒞 under a finite semigroup 𝑆 and elements
𝑥 1 , . . . , 𝑥 𝑘 ∈ 𝑆 by 𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ).
A Cayley circuit can be seen as a circuit in the usual sense: the finite semigroup 𝑆 and the
input gate values are given as part of the input and the functions computed by product gates
map a tuple, consisting of semigroup 𝑆 and two elements of 𝑆, to another element of 𝑆. We say
that a Cayley circuit with 𝑘 input gates can be simulated by a family of unbounded fan-in Boolean
circuits (𝒞𝑛 )𝑛∈ℕ if, given the encodings of a finite semigroup 𝑆 and of elements 𝑥 1 , . . . , 𝑥 𝑘 of 𝑆
of total length 𝑛, the circuit 𝒞𝑛 computes the encoding of 𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ). For a semigroup 𝑆
with 𝑁 elements, we assume that the elements of 𝑆 are encoded by the integers {0, . . . , 𝑁 − 1}
such that the encoding of a single element uses log 𝑁 bits. The semigroup itself is given as a
multiplication table with 𝑁 2 entries of log 𝑁 bits each.

Proposition 4.1. Let 𝒞 be a Cayley circuit of size 𝑚. Then, 𝒞 can be simulated by a family of unbounded
fan Boolean circuits (𝒞𝑛 )𝑛∈ℕ of depth 2 and size at most 𝑛 𝑚 .

Proof. Let 𝒞 be a Cayley circuit with 𝑘 input gates and 𝑚 − 𝑘 product gates. We want to construct
a Boolean circuit that can be used for all finite semigroups 𝑆 with a fixed number of elements 𝑁.
The input to such a circuit consists of 𝑛 = (𝑁 + 𝑘) log 𝑁 bits.
2

For a fixed vector (𝑦1 , . . . , 𝑦𝑚 ) ∈ 𝑆 𝑚 , one can check using a single AND gate (and additional
NOT gates at some of the incoming wires) whether (𝑦1 , . . . , 𝑦𝑚 ) corresponds to the sequence of
values occurring gates of 𝒞 under the given inputs. To this end, for each gate 𝑖 ∈ {1, . . . , 𝑚}
at the
of 𝒞, we add log 𝑁 incoming wires to this AND gate: if the 𝑖-th gate of 𝒞 is an input gate,
we feed the bits of the corresponding input value into the AND gate, complementing the 𝑗-th
bit if the 𝑗-th bit of 𝑦 𝑖 is zero. If the 𝑖-th gate is a product gate and has incoming wires from
gates ℓ and 𝑟, we connect the entry (𝑦ℓ , 𝑦𝑟 ) of the multiplication table to the AND gate, again
complementing bits corresponding to 0-bits of 𝑦 𝑖 .
To obtain a Boolean circuit simulating 𝒞, we put such AND gates for all vectors of the form
𝑚
(𝑦1 , . . . , 𝑦𝑚 ) ∈ 𝑆 in parallel. In a second layer, we create log 𝑁 OR gates and connect the
AND gate for a vector (𝑦1 , . . . , 𝑦𝑚 ) to the 𝑗-th OR gate if and only if the 𝑗-th bit of 𝑦𝑚 is one.
The idea is that exactly one of the AND gates — the gate corresponding to the vector of correct
guesses of the gate values of 𝒞 — evaluates to 1 and the corresponding output value 𝑦𝑚 then
occurs as output value of the OR gates. This circuit has depth 2 and size 𝑁 𝑚 + log 𝑁 ⩽ 𝑛 𝑚 .

4.2 The polylogarithmic circuits property
When analyzing the complexity of CSM(Ab), Barrington et al. introduced the so-called logarithmic
power basis property. A class of semigroups has the logarithmic power basis property if every set
𝑋 of generators for a semigroup 𝑆 of cardinality 𝑁 from the family has the property that every
element of 𝑆 can be written as a product of at most log(𝑁) many powers of elements of 𝑋. In [10],

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 8
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

it was shown that the class of Abelian groups has the logarithmic power basis property. Using a
different technique, this result can easily be extended to arbitrary commutative semigroups.

Lemma 4.2. The variety Com has the logarithmic power basis property.

Proof. Suppose that 𝑆 is a commutative semigroup of size 𝑁 and let 𝑋 be a set of generators for
𝑆. Let 𝑦 ∈ 𝑆 be an arbitrary element. We choose 𝑘 ∈ ℕ to be the smallest value such that there
𝑖
exist elements 𝑥 1 , . . . , 𝑥 𝑘 ∈ 𝑋 and integers 𝑖1 , . . . , 𝑖 𝑘 ∈ ℕ with 𝑦 = 𝑥1𝑖1 · · · 𝑥 𝑘𝑘 . Assume, for the
sake of contradiction, that 𝑘 > log(𝑁).
The power set 𝒫({1, . . . , 𝑘}) forms a semigroup when equipped with set union as binary
𝑖𝑗
operation. Consider the morphism ℎ : 𝒫({1, . . . , 𝑘}) → 𝑆 defined by ℎ({𝑗}) = 𝑥 𝑗 for all
𝑗 ∈ {1, . . . , 𝑘}. This morphism is well-defined because 𝑆 is commutative.
Since |𝒫({1, . . . , 𝑘})| = 2 𝑘 > 2log(𝑁) = |𝑆|, we know by the pigeonhole principle that there
exist two sets 𝐾1 , 𝐾2 ⊆ {1, . . . , 𝑘} with 𝐾1 ≠ 𝐾 2 and ℎ(𝐾 1 ) = ℎ(𝐾2 ). We may assume, without
loss of generality, that there exists some 𝑗 ∈ 𝐾 1 \ 𝐾 2 . Now, because

𝑦 = ℎ({1, . . . , 𝑘}) = ℎ(𝐾 1 ) ℎ({1, . . . , 𝑘} \ 𝐾 1 ) = ℎ(𝐾2 ) ℎ({1, . . . , 𝑘} \ 𝐾1 )

and since neither 𝐾 2 nor {1, . . . , 𝑘} \ 𝐾 1 contain 𝑗, we know that 𝑦 can be written as a product of
powers of elements 𝑥 𝑖 with 1 ⩽ 𝑖 ⩽ 𝑘 and 𝑖 ≠ 𝑗, contradicting the choice of 𝑘.
For the analysis of arbitrary groups, we introduce a more general concept. It is based
on the idea that algebraic circuits (Cayley circuits with fixed inputs) can be used for succinct
representations of semigroup elements.

Example 4.3 (repeated squaring). Let 𝑒 ∈ ℕ be a positive integer. Then, one can construct
a Cayley circuit of size at most 2 log 𝑒 which computes, given a finite semigroup 𝑆 and an
element 𝑥 ∈ 𝑆 as input, the power 𝑥 𝑒 in 𝑆. If 𝑒 = 1, the circuit only consists of the input gate. If 𝑒
is even, the circuit is obtained by taking the circuit for 𝑒/2, adding a product gate and creating
two edges from the output gate of the circuit for 𝑒/2 to the new gate. If 𝑒 is odd, the circuit is
obtained by taking the circuit for 𝑒 − 1 and connecting it to a new product gate. In this case, the
second incoming edge for the new gate comes from the input gate.

A class of semigroups has the polylogarithmic circuits property if there exists a constant 𝑐 ∈ ℕ
such that for each semigroup 𝑆 of cardinality 𝑁 from the class, for each subset 𝑋 of 𝑆 and for
each 𝑦 in the subsemigroup generated by 𝑋, there exists a Cayley circuit 𝒞 of size log𝑐 (𝑁) with
𝑘 input gates and there exist 𝑥 1 , . . . , 𝑥 𝑘 ∈ 𝑋 such that 𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ) = 𝑦.
For classes closed under taking subsemigroups, such as varieties of finite semigroups, this is
equivalent to saying that each element 𝑦 of a semigroup of cardinality 𝑁 can be represented by
a Cayley circuit of size log𝑐 (𝑁) over any set of generators. Alternatively, the polylogarithmic
circuits property can be defined in terms of straight-line programs; this connection will be used
further below.

Proposition 4.4. Let C be a family of semigroups that is closed under subsemigroups and has the
logarithmic power basis property. Then C has the polylogarithmic circuits property.

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 9
L UKAS F LEISCHER

𝒞1 𝒞2 𝒞𝑘
𝑥1 𝑥2 𝑥𝑘

· · ·

𝒟

Figure 1: The Cayley circuit 𝒞 from Proposition 4.4

Proof. Let 𝑋 be a subset of a semigroup 𝑆 of cardinality 𝑁. Let 𝑦 be in the subsemigroup
𝑖
generated by 𝑋. Then, we have 𝑦 = 𝑥 1𝑖1 · · · 𝑥 𝑘𝑘 for some 𝑥1 , . . . , 𝑥 𝑘 ∈ 𝑋 with 𝑘 ⩽ log(𝑁) and
𝑖1 , . . . , 𝑖 𝑘 ∈ ℕ . By the pigeonhole principle, we may assume without loss of generality that
1 ⩽ 𝑖1 , . . . , 𝑖 𝑘 ⩽ 𝑁. Usingthe method from Example 4.3, one can construct Cayley circuits
𝒞1 , . . . , 𝒞𝑘 of size at most 2 log 𝑁 such that 𝒞𝑗 (𝑆, 𝑥) = 𝑥 𝑖 𝑗 for all 𝑗 ∈ {1, . . . , 𝑘} and 𝑥 ∈ 𝑆. Using

𝑘 − 1 additional product gates 𝒟, these circuits can be combined to a single circuit 𝒞 with
𝑖
𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ) = 𝑥 1𝑖1 · · · 𝑥 𝑘𝑘 = 𝑦. The construction is depicted in Figure 1.
In total, the resulting circuit consists of 𝑘 · 2 log 𝑁 + 𝑘 − 1 < 5 log2 (𝑁) gates.

Let 𝐺 be a finite group and let 𝑋 be a subset of 𝐺. A sequence (𝑔1 , . . . , 𝑔ℓ ) of elements of 𝐺
is a straight-line program over 𝑋 if for each 𝑖 ∈ {1, . . . , ℓ }, we have 𝑔 𝑖 ∈ 𝑋 or 𝑔 𝑖 = 𝑔 𝑝−1 or 𝑔 𝑖 = 𝑔 𝑝 𝑔 𝑞
for some 𝑝, 𝑞 < 𝑖. The number ℓ is the length of the straight-line program and the elements of
the sequence are said to be generated by the straight-line program. The following result by Babai
and Szemerédi [6] is commonly known as the Reachability Lemma.
Lemma 4.5 (Reachability Lemma). Let 𝐺 be a finite group and let 𝑋 be a set of generators of 𝐺. Then,
for each element 𝑡 ∈ 𝐺, there exists a straight-line program over 𝑋 generating 𝑡 which has length at most
(log |𝐺| + 1)2 .
The proof of this lemma is based on a technique called “cube doubling”. For details, we
refer to [3]. It is now easy to see that groups admit polylogarithmic circuits.
Lemma 4.6. The variety G has the polylogarithmic circuits property.
Proof. Let 𝐺 be a group of order 𝑁, let 𝑋 be a subset of 𝐺 and let 𝑦 be an element in the
subgroup of 𝐺 generated by 𝑋. By Lemma 4.5, we know that there exists a straight-line program

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 10
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

(𝑔1 , . . . , 𝑔ℓ ) over 𝑋 with ℓ ⩽ (log(𝑁) + 1)2 and 𝑔ℓ = 𝑦. We may assume that the elements
𝑔1 , . . . , 𝑔ℓ are pairwise distinct. It suffices to describe how to convert this straight-line program
into a Cayley circuit 𝒞 and values 𝑥 1 , . . . , 𝑥 𝑘 ∈ 𝑋 such that 𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ) = 𝑦.
We start with an empty circuit and with 𝑘 = 0 and process the elements of the straight-line
program left to right. For each element 𝑔 𝑖 , we add gates to the circuit. The output gate of the
circuit obtained after processing the element 𝑔 𝑖 will be called the 𝑔 𝑖 -gate.
If the current element 𝑔 𝑖 is contained in 𝑋, we increment 𝑘, add a new input gate to the
circuit and let 𝑥 𝑘 = 𝑔 𝑖 . If the current element 𝑔 𝑖 can be written as a product 𝑔 𝑝 𝑔 𝑞 with 𝑝, 𝑞 < 𝑖, we
add a new product gate to the circuit and connect the 𝑔 𝑝 -gate as well as the 𝑔 𝑞 -gate to this new
gate. If the current element 𝑔 𝑖 is an inverse 𝑔 𝑝−1 with 𝑝 < 𝑖, we take a circuit 𝒞 0 with 2 log 𝑁

gates and with 𝒞 0(𝐺, 𝑥) = 𝑥 𝑁−1 for all 𝑥 ∈ 𝑆. Such a circuit can be built by using the powering
technique illustrated in Example 4.3. We add 𝒞 0 to 𝒞, replacing its input gate by an edge coming
from the 𝑔 𝑝 -gate.
The resulting circuit has size at most (log(𝑁) + 1)2 · 2 log 𝑁 ⩽ 2(log(𝑁) + 1)3 .

We will now show that for classes of semigroups with the polylogarithmic circuits property,
one can solve the Cayley semigroup membership problem in qAC0 .

Theorem 4.7. Let C be a class of semigroups with the polylogarithmic circuits property. Then CSM(C)
is in qAC0 .

Proof. We construct a family of unbounded fan-in constant-depth Boolean circuits with quasi-
polynomial size, deciding, given the multiplication table of a semigroup 𝑆 ∈ C, a set 𝑋 ⊆ 𝑆 and
an element 𝑡 ∈ 𝑆 as inputs, whether 𝑡 is in the subsemigroup generated by 𝑋.
Since C has the polylogarithmic circuits property, we know that, for some constant 𝑐 ∈ ℕ ,
the element 𝑡 is in the subsemigroup generated by 𝑋 if and only if there exist a Cayley circuit
𝒞 of size log𝑐 (𝑛) and inputs 𝑥 1 , . . . , 𝑥 𝑘 ∈ 𝑋 such that 𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ) = 𝑡. There are at most
𝑐 𝑐
(log𝑐 (𝑛) · log𝑐 (𝑛))log (𝑛) = 22𝑐 log (𝑛) log log(𝑛) different Cayley circuits of this size. Let us consider
one of these Cayley circuits 𝒞. Suppose that 𝒞 has 𝑘 input gates. By Proposition 4.1, there
𝑐 𝑐+1
exists an unbounded fan-in constant-depth Boolean circuit of size 𝑛 log 𝑛 = 2log 𝑛 deciding
on input 𝑆 and elements 𝑥1 , . . . , 𝑥 𝑘 ∈ 𝑆 whether 𝒞(𝑆, 𝑥1 , . . . , 𝑥 𝑘 ) = 𝑡. There are at most
𝑐 𝑐+1
𝑛 𝑘 ⩽ 𝑛 log 𝑛 = 2log 𝑛 possibilities of connecting (not necessarily all) input gates corresponding
to the elements of 𝑋 to this simulation circuit.
Thus, we can check for all Cayley circuits of the given size and all possible input assignments
in parallel, whether the value of the corresponding circuit is 𝑡, and feed the results of all these
checks into a single OR gate to obtain a quasi-polynomial-size Boolean circuit.
In conjunction with Lemma 4.2 and Lemma 4.6, we immediately obtain the following
corollary.

Corollary 4.8. Both CSM(G) and CSM(Com) are contained in qAC0 .

As stated in the preliminaries, problems in qAC0 cannot be hard for any complexity class
containing Parity. Thus, we also obtain the following statement.

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 11
L UKAS F LEISCHER

Corollary 4.9. Let C be a class of semigroups with the polylogarithmic circuits property, such as the
variety of finite groups G or the variety of finite commutative semigroups Com. Then CSM(C) is
not hard, under AC0 reductions, for any complexity class containing Parity, such as ACC0 , TC0 , NC1 ,
Logspace or NL.

4.3 Connections to FOLL
In a first attempt to solve outstanding complexity questions related to the Cayley semigroup
membership problem, Barrington et al. introduced the complexity class FOLL. The approach
presented in the present paper is quite different. This raises the question of whether our
techniques can be used to design FOLL-algorithms for Cayley semigroup membership. Note
that FOLL and qAC0 are known to be incomparable, so we cannot use generic results from
complexity theory to simulate qAC0 circuits using families of FOLL circuits or vice versa. The
direction FOLL * qAC0 follows from bounds on the average sensitivity of bounded-depth circuits
(Boppana [15]); using these bounds, one can show that there exists a padded version of the
Parity function that can be computed by a FOLL circuit family and cannot be computed by any
qAC0 circuit family. Conversely, each subset of {0, 1} 𝑛 of cardinality at most 𝑛 log 𝑛 is decidable
by a depth-2 circuit of size 𝑛 1+log 𝑛 + 1, but for each fixed 𝑘 ∈ ℕ , there is some large value 𝑛 ⩾ 1
such that the number of such subsets exceeds the number of different circuits of size 𝑛 𝑘 . This
shows that there exist languages in qAC0 that are not contained in P/poly ⊇ FOLL.
Designing an FOLL-algorithm that works for arbitrary classes of semigroups with the
polylogarithmic circuits property seems difficult. However, for certain special cases, there is an
interesting approach, based on the repeated squaring technique. We first give an interpretation
of the Double-Barrelled Recursive Strategy from [10] in the Cayley circuit setting.
Suppose we are given a cyclic group of large order 𝑁, generated by the element 𝑥, and
some integer 𝑒 ∈ {1, . . . , 𝑁 }. Let ℓ = log 𝑒 be the length of the binary representation of

𝑒. The element 𝑥 𝑒 can be computed by a repeated squaring Cayley circuit as described in
Example 4.3. These circuits only use two different “types” of product gates: gates squaring the
current intermediate result and gates multiplying the intermediate result by the generator 𝑥.
When viewed as operations on the exponent of 𝑥, the first gate type performs a left shift of the
exponent by 1 bit whereas the second gate type toggles the last bit of an even exponent. Clearly,
the integer 𝑒 can be generated by a sequence of at most 2ℓ of these operations. The idea of the
Double-Barrelled Recursive Strategy is that, instead of performing these shift-toggle operations
on the exponent 𝑒 sequentially, we can split its binary representation into two parts of roughly
the same size. This yields values 𝑒1 and 𝑒2 with dℓ /2e bits each such that 𝑒 = 𝑒1 · 2 dℓ /2e + 𝑒2 . The
value 𝑒1 can be guessed. Then, we recursively run the same procedure to confirm that 𝑒1 can
be obtained from 𝑥 by a sequence of ℓ operations and that 𝑒 can be obtained from 𝑒1 in the
same way. In each recursion step, the number of required operations is halved. Therefore, the
recursion depth is log(2ℓ ) ∈ 𝒪(log log 𝑁).
In the Cayley circuit, this strategy corresponds to dividing the circuit into two parts of
roughly equal size and handling the two parts recursively. This idea also works whenever the
gates of a Cayley circuit can be ordered in a way such that the number of gate values produced
by the first 𝑖 gates and reused by the remaining gates is bounded by a constant. This property is

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 12
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

formalized and used to describe a more general FOLL algorithm below.
For a Cayley circuit, the width of a topological ordering (𝑣 1 , . . . , 𝑣 𝑚 ) of the gates is the smallest
number 𝑤 ∈ ℕ such that for each 𝑖 ∈ {1, . . . , 𝑚 − 1}, at most 𝑤 product gates from the set
𝐴 𝑖 = {𝑣 1 , . . . , 𝑣 𝑖 } are connected to gates in 𝐵 𝑖 = {𝑣 𝑖+1 , . . . , 𝑣 𝑚 }. Let 𝐶 𝑖 be the set of product
gates belonging to 𝐴 𝑖 that are connected to gates in 𝐵 𝑖 . The subcircuit induced by 𝐴 𝑖 can be
interpreted as a Cayley circuit computing multiple output values 𝐶 𝑖 . The subcircuit induced by
𝐵 𝑖 can be seen as a circuit which, in addition to the input gates of the original circuit, uses the
gates from 𝐶 𝑖 as input gates. The width of a Cayley circuit is the smallest width of a topological
ordering of its gates. Let us fix some width 𝑤 ∈ ℕ .
We introduce a predicate 𝑃(𝑧 1 , . . . , 𝑧 𝑤 , 𝑦1 , . . . , 𝑦𝑤 , 𝑖) which is true if there exists a Cayley
circuit of width at most 𝑤 and size at most 2𝑖 with 𝑤 additional input gates and 𝑤 additional
passthrough gates (which have in-degree 1 and replicate the value of their predecessors), such that
the elements 𝑦1 , . . . , 𝑦𝑤 ∈ 𝑆 occur as values of the passthrough gates when using 𝑧 1 , . . . , 𝑧 𝑤 ∈ 𝑆
as values for the additional input gates and using any subset of the original inputs 𝑋 as values
for the remaining input gates. The additional input gates (or passthrough gates) are not counted
when measuring the circuit size but are considered as product gates when measuring width
and they have to be the first (last, resp.) gates in all topological orderings considered for width
measurement. For each fixed 𝑖, there are only 𝑛 2𝑤 such predicates.
The truth value of a predicate with 𝑖 = 0 can be computed by a constant-depth un-
bounded fan-in Boolean circuit of polynomial size. This is achieved by computing all binary
products of the elements 𝑧 1 , . . . , 𝑧 𝑤 and elements of the input set 𝑋. For 𝑖 ⩾ 1, the predi-
cate 𝑃(𝑧 1 , . . . , 𝑧 𝑤 , 𝑦1 , . . . , 𝑦𝑤 , 𝑖) is true if and only if there exist 𝑧10 , . . . , 𝑧 0𝑤 ∈ 𝑆 such that both
𝑃(𝑧 1 , . . . , 𝑧 𝑤 , 𝑧10 , . . . , 𝑧 0𝑤 , 𝑖 − 1) and 𝑃(𝑧 10 , . . . , 𝑧 0𝑤 , 𝑦1 , . . . , 𝑦𝑤 , 𝑖 − 1) are true. Having the truth
values of all tuples for 𝑖 − 1 at hand, this can be checked with a polynomial number of gates in
constant depth because there are only 𝑛 𝑤 different vectors (𝑧 10 , . . . , 𝑧 0𝑤 ) ∈ 𝑆 𝑤 .
For a class of semigroups C with Cayley circuits of bounded width and polylogarithmic size,
we obtain a circuit family of depth 𝒪(log log 𝑛) deciding CSM(C): the predicates are computed
for increasing values of 𝑖, until 𝑖 exceeds the logarithm of an upper bound for the Cayley circuit
size and then, we return 𝑃(𝑥, . . . , 𝑥, 𝑡, . . . , 𝑡, 𝑖) for the element 𝑡 given in the input and for an
arbitrary element 𝑥 ∈ 𝑋. The number of repetitions of both 𝑥 and 𝑡 in 𝑃(𝑥, . . . , 𝑥, 𝑡, . . . , 𝑡, 𝑖) is 𝑤.
One example of Cayley circuits of bounded width are the circuits constructed in the proof
of Proposition 4.4. Recall that those circuits consist of subcircuits 𝒞1 , . . . , 𝒞𝑘 and additional
product gates 𝒟. Let 𝑑2 denote the gate computing the product of the output values of 𝒞1 and
𝒞2 . For 𝑗 ∈ {3, . . . , 𝑘}, let 𝑑 𝑗 denote the gate computing the product of 𝑑 𝑗−1 and the output value
of 𝒞𝑗 . Now consider the topological ordering with all gates from 𝒞𝑖 preceding all gates from
𝒞𝑗 for 𝑖 < 𝑗 and with each of the additional multiplication gates from 𝒟 as early as possible,
i. e., the sequence starts with the gates from 𝒞1 , followed by 𝒞2 , 𝑑2 , . . . , 𝒞𝑘 , 𝑑 𝑘 . This ordering has
width at most 2. In particular, we obtain a self-contained proof of the following result.

Theorem 4.10. Let C be a class of semigroups that is closed under taking subsemigroups and has the
logarithmic power basis property. Then CSM(C) is in FOLL.

By Lemma 4.2, we obtain the following corollary.

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 13
L UKAS F LEISCHER

Corollary 4.11. CSM(Com) is contained in FOLL.

4.4 The complexity landscape of Cayley semigroup membership
Little is known about when there are algorithms more efficient than the qAC0 or FOLL upper
bounds given in the previous sections. We will now describe an interesting special case for
which the Cayley semigroup membership problem is in AC0 .

Theorem 4.12. For each 𝑘 ⩾ 1, CSM(LI 𝑘 ) is contained in AC0 .

Proof. Let 𝑘 ∈ ℕ be fixed. Then, for a given input set 𝑋 of cardinality at most 𝑁, there are at
most |𝑋 | 2𝑘 ⩽ 𝑁 2𝑘 different products of the form 𝑥1 · · · 𝑥 𝑘 𝑦 𝑘 · · · 𝑦1 with 𝑥 1 , . . . , 𝑥 𝑘 , 𝑦1 , . . . , 𝑦 𝑘 ∈ 𝑋.
By the definition of LI 𝑘 , the element 𝑡 belongs to the subsemigroup of 𝑆 generated by 𝑋 if and
only if it is equal to one of these products. We can compute all these products with polynomially
many gates in constant depth. Then, we compare each of the results with 𝑡.
Ð
We recall that the union 𝑘∈ℕ LI 𝑘 is the variety of all locally trivial semigroups, which is
Ð
known to properly contain N. Thus, CSM( 𝑘∈ℕ LI 𝑘 ) is NL-complete by Theorem 3.2. This
implies that there is no class of finite semigroups that covers all (and only those) varieties of
finite semigroups for which Cayley Semigroup Membership is in AC0 . If C is any class containing
all varieties V with CSM(V) ∈ AC0 , then CSM(C) is as hard as in the general case.
The previous construction strongly relies on the fact that the classes LI 𝑘 contain only
semigroups without a neutral element. However, a slightly weaker statement also holds for
varieties of finite monoids. It relies on the following result, which can be seen as a consequence
of [1] and the fact that the zero element in a semigroup is always central. For completeness, we
provide a short and self-contained proof.

Proposition 4.13. The variety N is included in G ∨ Com.

Proof. We show that every finite nilpotent semigroup divides a direct product of a finite group
and a finite commutative semigroup. Note that in a finite nilpotent semigroup 𝑆, there exists an
integer 𝑒 ⩾ 0 such that for each 𝑥 ∈ 𝑆, the power 𝑥 𝑒 is the zero element. Let 𝑇 = {1, . . . , 𝑒} be
the commutative semigroup with the product of two elements 𝑖 and 𝑗 defined as min {𝑖 + 𝑗, 𝑒}.
Let 𝑋 be the set of non-zero elements of 𝑆 and let 𝐹(𝑋) be the free group over 𝑋. For an
element 𝑤 ∈ 𝐹(𝑋), we use 𝑤 to denote its inverse. We use |𝑤| to denote the length of the (freely
reduced) normal form of 𝑤. Since 𝐹(𝑋) is residually finite [23, 24], for each 𝑤 ∈ 𝐹(𝑋) \ {1}, there
exist a finite group 𝐺𝑤 and morphism 𝜓𝑤 : 𝐹(𝑋) → 𝐺𝑤 such that 𝜓𝑤 (𝑤) ≠ 1. Let 𝐺 be the direct
product of all groups 𝐺𝑤 for |𝑤| < 2𝑒 − 1 and let 𝜓 : 𝐹(𝑋) → 𝐺 be the product morphism of the
corresponding morphisms 𝜓𝑤 . Note that for 𝑢, 𝑣 ∈ 𝑋 ∗ with |𝑢| , |𝑣| < 𝑒, we have 𝜓(𝑢) ≠ 𝜓(𝑣):
if 𝜓(𝑢) were equal to 𝜓(𝑣), we would have 𝜓(𝑢𝑣) = 1, and thus 𝜓𝑢𝑣 (𝑢𝑣) = 1, contradicting the
choice of 𝜓𝑢𝑣 .
Let 𝑈 be the subsemigroup of 𝐺 × 𝑇 generated by {(𝜓(𝑥), 1) | 𝑥 ∈ 𝑋}. Now, we define a
mapping 𝜑 : 𝑈 → 𝑆 as follows. Each element of the form (𝑔, 𝑒) is mapped to zero. For every
(𝑔, ℓ ) ∈ 𝑈 with ℓ < 𝑒, there exists, by choice of 𝜓 and by the definition of 𝑈, a unique factorization

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 14
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

𝑔 = 𝜓(𝑥 1 · · · 𝑥ℓ ) with 𝑥 1 , . . . , 𝑥ℓ ∈ 𝑋. We map (𝑔, ℓ ) to the product 𝑥 1 · · · 𝑥ℓ evaluated in 𝑆. It is
straightforward to verify that 𝜑 is a surjective morphism and thus, 𝑆 is a quotient of 𝑈.
Corollary 4.14. There exist two varieties of finite monoids V and W such that both CSM(V) and
CSM(W) are contained in qAC0 (and thus not hard for any class containing Parity) but CSM(V ∨ W)
is NL-complete.
The corollary is a direct consequence of the previous proposition, Corollary 4.8 and
Theorem 3.2. As was observed in [10] already, Cayley semigroup problems seem to have
“strange complexity”. The results in this section make this intuition more concrete and suggest
that it is difficult to find “nice” descriptions of maximal classes of semigroups for which the
Cayley semigroup membership problem is easier than any NL-complete problem.

5 Summary and outlook
We provided new insights into the complexity of the Cayley semigroup membership problem
for classes of finite semigroups, giving parallel algorithms for the variety of finite commutative
semigroups and the variety of finite groups. We also showed that a maximal class of semigroups
with Cayley semigroup membership decidable by qAC0 circuits does not form a variety.
Afterwards, we discussed applicability to FOLL and gave examples of classes for which the
problem is in AC0 .
It is tempting to ask whether one can find nice connections between algebra and the
complexity of the Cayley semigroup membership problem by conducting a more fine-grained
analysis. Does the maximal class of finite semigroups, for which the Cayley semigroup
membership problem is in AC0 , form a variety of finite semigroups? Is it possible to show
that AC0 does not contain CSM(G) or CSM(Com)? Potential approaches to tackling the latter
question are reducing small distance connectivity for paths of non-constant length [16] to
CSM(G) or developing a suitable switching lemma. Another related question is whether there
exist classes of semigroups for which the Cayley semigroup membership problem cannot be
NL-hard but, at the same time, is not contained within qAC0 .
Moreover, it would be interesting to see whether the Cayley semigroup membership problem
can be shown to be in FOLL for all classes of semigroups with the polylogarithmic circuits
property. More generally, investigating the relationship of FOLL and qAC0 to other complexity
classes remains an interesting subject for future research.
Finally, we wish to point out that while we have shown that the Cayley semigroup membership
problem for groups is not hard for Logspace under AC0 reductions, it remains open whether it
is Logspace-complete under NC1 reductions.

Acknowledgements. I would like to thank Armin Weiß, Samuel Schlesinger, and Madhur
Tulsiani for discussions and comments that led to significant improvements of the presentation
of the paper. Special thanks to Armin Weiß for pointing out that qAC0 is not contained within
P/poly, to Samuel Schlesinger for pointing out that results on the average sensitivity of bounded-
depth circuits can be used to show that FOLL is not contained within qAC0 , and to Madhur

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 15
L UKAS F LEISCHER

Tulsiani for pointing out a direct application of the Black Box Group model in the Cayley table
setting. Moreover, I am grateful to the anonymous referees of both the conference and the full
version of this paper for providing helpful comments.

References
[1] Jorge Almeida: Some pseudovariety joins involving the pseudovariety of finite groups.
Semigroup Forum, 37(1):53–57, 1988. [doi:10.1007/BF02573123] 14
[2] László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429.
ACM Press, 1985. [doi:10.1145/22145.22192] 3
[3] László Babai: Local expansion of vertex-transitive graphs and random generation in finite
groups. In Proc. 23rd STOC, pp. 164–174. ACM Press, 1991. [doi:10.1145/103418.103440] 10
[4] László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, and Eugene M. Luks: Multiplicative
equations over commuting matrices. In Proc. 7th Ann. ACM–SIAM Symp. on Discrete
Algorithms (SODA’96), pp. 498–507. SIAM, 1996. ACM DL. 3
[5] László Babai, Eugene M. Luks, and Ákos Seress: Permutation groups in NC. In Proc. 19th
STOC, pp. 409–420. ACM Press, 1987. [doi:10.1145/28395.28439] 3
[6] László Babai and Endre Szemerédi: On the complexity of matrix group problems I. In Proc.
25th FOCS, pp. 229–240. IEEE Comp. Soc., 1984. [doi:10.1109/SFCS.1984.715919] 3, 7, 10
[7] David A. Mix Barrington: Bounded-width polynomial-size branching programs recognize
exactly those languages in NC1 . J. Comput. System Sci., 38(1):150–164, 1989. Preliminary
version in STOC’86. [doi:10.1016/0022-0000(89)90037-8] 3
[8] David A. Mix Barrington and Pierre McKenzie: Oracle branching programs and
Logspace versus P. Inform. Comput., 95(1):96–115, 1991. Preliminary version in MFCS’89.
[doi:10.1016/0890-5401(91)90017-V] 2, 3
[9] David A. Mix Barrington and Denis Thérien: Finite monoids and the fine structure of 𝑁 𝐶 1 .
J. ACM, 35(4):941–952, 1988. Preliminary version in STOC’87. [doi:10.1145/48014.63138] 3
[10] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, and Pierre McKenzie: On the
complexity of some problems on groups input as multiplication tables. J. Comput. System
Sci., 63(2):186–200, 2001. Preliminary version in CCC’00. [doi:10.1006/jcss.2001.1764] 2, 3,
4, 8, 12, 15
[11] Martin Beaudry: Membership Testing in Transformation Monoids. Ph. D. thesis, McGill
University, 1987. eScholarship@McGill. 3
[12] Martin Beaudry: Membership testing in commutative transformation semigroups. In-
form. Comput., 79(1):84–93, 1988. Preliminary version in ICALP’87. [doi:10.1016/0890-
5401(88)90018-1] 3

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 16
T HE C AYLEY S EMIGROUP M EMBERSHIP P ROBLEM

[13] Martin Beaudry: Membership testing in threshold one transformation monoids. Inform.
Comput., 113(1):1–25, 1994. [doi:10.1006/inco.1994.1062] 3

[14] Martin Beaudry, Pierre McKenzie, and Denis Thérien: The membership problem in aperi-
odic transformation monoids. J. ACM, 39(3):599–616, 1992. [doi:10.1145/146637.146661]
3

[15] Ravi B. Boppana: The average sensitivity of bounded-depth circuits. Inform. Process. Lett.,
63(5):257–261, 1997. [doi:10.1016/S0020-0190(97)00131-2] 12

[16] Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan: Near-optimal
small-depth lower bounds for small distance connectivity. In Proc. 48th STOC, pp. 612–625.
ACM Press, 2016. [doi:10.1145/2897518.2897534, arXiv:1509.07476] 15

[17] Lukas Fleischer: On the complexity of the Cayley semigroup membership problem. In Proc.
33rd Comput. Complexity Conf. (CCC’18), pp. 25:1–12. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.25] 1

[18] Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks: Polynomial-time algo-
rithms for permutation groups. In Proc. 21st FOCS, pp. 36–41. IEEE Comp. Soc., 1980.
[doi:10.1109/SFCS.1980.34] 3

[19] Johan Håstad: Almost optimal lower bounds for small depth circuits. In Proc. 18th STOC,
pp. 6–20. ACM Press, 1986. [doi:10.1145/12130.12132] 5

[20] John M. Howie: Fundamentals of Semigroup Theory. Clarendon Press, 1995. 5

[21] Neil D. Jones and William T. Laaser: Complete problems for deterministic polynomial time.
Theoret. Comput. Sci., 3(1):105–117, 1976. Preliminary version in STOC’74. [doi:10.1016/0304-
3975(76)90068-2] 2, 3

[22] Neil D. Jones, Y. Edmund Lien, and William T. Laaser: New problems complete for
nondeterministic log space. Math. Sys. Theory, 10(1):1–17, 1976. [doi:10.1007/BF01683259]
2, 3, 4, 6

[23] Friedrich Levi: Über die Untergruppen der freien Gruppen. (2. Mitteilung). Mathematische
Zeitschrift, 37:90–97, 1933. EuDML. 14

[24] Roger C. Lyndon and Paul E. Schupp: Combinatorial Group Theory. Springer, 2001.
[doi:10.1007/978-3-642-61896-3] 14

[25] Jean-Éric Pin: Varieties of Formal Languages. North Oxford Academic, 1986. 5

[26] Omer Reingold: Undirected connectivity in Log-space. J. ACM, 55(4):17:1–24, 2008.
Preliminary version in STOC’05. [doi:10.1145/1391289.1391291] 3

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 17
L UKAS F LEISCHER

[27] Charles C. Sims: Computational methods in the study of permutation groups. In
Computational Problems in Abstract Algebra, pp. 169–183. Pergamon, 1970. See also SYMSAC’71.
[doi:10.1016/B978-0-08-012975-4.50020-5] 3

[28] Heribert Vollmer: Introduction to Circuit Complexity. Springer, 1999. [doi:10.1007/978-3-
662-03927-4] 5

[29] Andrew Chi-Chih Yao: Separating the polynomial-time hierarchy by oracles. In Proc. 26th
FOCS, pp. 1–10. IEEE Comp. Soc., 1985. [doi:10.1109/SFCS.1985.49] 5

AUTHOR

Lukas Fleischer
lfleischer lfos de
https://lfos.de/

ABOUT THE AUTHOR

Lukas Fleischer received his Ph. D. at the University of Stuttgart, supervised by
Volker Diekert, where his research focused on algorithmic and complexity aspects
of finite semigroups. In 2019, he was a postdoctoral researcher in the Cheriton
School of Computer Science at the University of Waterloo, working with Jeffrey
Shallit. Lukas is now working as a software engineer in Kitchener–Waterloo. In
his free time, he enjoys contributing to open source projects. He is also interested
in technology, investing, entrepreneurship, sustainability, health, and fitness.

T HEORY OF C OMPUTING, Volume 18 (8), 2022, pp. 1–18 18