Abstract 1 Introduction 2 Preliminaries and Notation 3 Membership and Conjugacy in Groups 4 Membership and Conjugacy in Clifford Semigroups 5 Membership and Conjugacy in Strict Inverse Semigroups 6 Inverse Semigroups in the Cayley Table Model 7 Inverse Semigroups in the Partial Bijection Model 8 Further Related Problems 9 Discussion and Open Problems References

Membership and Conjugacy in Inverse Semigroups

Lukas Fleischer ORCID FMI, University of Stuttgart, Germany Florian Stober ORCID FMI, University of Stuttgart, Germany Alexander Thumm ORCID University of Siegen, Germany Armin Weiß ORCID FMI, University of Stuttgart, Germany
Abstract

The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be 𝖯𝖲𝖯𝖠𝖢𝖤-complete in the transformation model by Kozen (1977) and 𝖭𝖫-complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be 𝖯𝖲𝖯𝖠𝖢𝖤-complete in the partial bijection model by Jack (2023).

Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in 𝖭𝖢 (resp. 𝖭𝖯 for conjugacy) for strict inverse semigroups and 𝖯𝖲𝖯𝖠𝖢𝖤-complete otherwise. In the Cayley table model we obtain general 𝖫-algorithms as well as 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 upper bounds for Clifford semigroups and 𝖫-completeness otherwise.

Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is 𝖯𝖲𝖯𝖠𝖢𝖤-complete even for automata with only two states; the subpower membership problem is in 𝖭𝖢 for every strict inverse semigroup and 𝖯𝖲𝖯𝖠𝖢𝖤-complete otherwise; the minimum generating set and the equation satisfiability problems are in 𝖭𝖯 for varieties of finite strict inverse semigroups and 𝖯𝖲𝖯𝖠𝖢𝖤-complete otherwise.

Keywords and phrases:
inverse semigroups, membership, conjugacy, finite automata
Category:
Track B: Automata, Logic, Semantics, and Theory of Programming
Funding:
Armin Weiß: Supported by the German Research Foundation (DFG) grant WE 6835/1-2.
Copyright and License:
[Uncaptioned image] © Lukas Fleischer, Florian Stober, Alexander Thumm, and Armin Weiß; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Algebraic language theory
; Theory of computation Problems, reductions and completeness ; Theory of computation Circuit complexity
Related Version:
Full Version: https://arxiv.org/abs/2502.10103 [24]
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

In this work, we study the membership problem for inverse semigroups and some related problems such as the conjugacy problem. The membership problem for semigroups in the transformation model has first been studied by Kozen [40] in 1977. It receives as input a list (u1,,uk) of functions ui:ΩΩ for some finite set Ω and a target function t:ΩΩ; the question is whether t can be written as composition of the ui or, with other words, whether t is contained in the subsemigroup generated by {u1,,uk}. It is closely related to the DFA intersection non-emptiness problem, which receives as input a list of deterministic finite automata (DFAs) and asks whether there is a word accepted by all of the automata. Indeed, Kozen [40] showed that both problems are 𝖯𝖲𝖯𝖠𝖢𝖤-complete.

Inverse semigroups have first been studied by Wagner [64] and Preston [54] to describe partial symmetries. They constitute the arguably most natural class of algebraic structures containing groups and being contained in the semigroups. An inverse semigroup is a semigroup equipped with an additional unary operation xx¯ such that xx¯x=x and x¯xx¯=x¯ for all x and x¯ is unique with that property. This clearly generalizes the inverse operation in groups. Similar to groups being an algebraic abstraction of symmetries and semigroups being an algebraic abstraction of computation, inverse semigroups abstract symmetric computation. This notion of computation, where every computational step is invertible, was introduced by Lewis and Papadimitriou [43] in order to better describe the complexity of the accessibility problem in undirected graphs ugap, which only much later was shown to be in 𝖫 (deterministic logspace) by Reingold [55].

In the setting of inverse semigroups, it is natural to consider the partial bijection model for the membership problem, where the ui and t are partial functions which are injective on their domain. The membership problem for inverse semigroups in the partial bijection model is also 𝖯𝖲𝖯𝖠𝖢𝖤-complete – and, thus, as difficult as for arbitrary semigroups – as Jack [33] recently observed. This observation is based on a result by Birget, Margolis, Meakin, and Weil [11] showing that the intersection non-emptiness problem for inverse automata is 𝖯𝖲𝖯𝖠𝖢𝖤-complete. Roughly speaking, an inverse automaton is a DFA with a partially defined transition function where every letter induces a partial bijection on the set of states and the action of each letter can be “inverted” by a sequence of letters. Thus, inverse automata can be seen as a generalization of permutation automata, for which the intersection non-emptiness problem is 𝖭𝖯-complete [12]. Interestingly, the corresponding membership problem for permutation groups is even in 𝖭𝖢 as shown by Babai, Luks, and Seress [5] after a series of partial results [59, 25, 47, 45, 49, 4].

A different variant of the membership problem has been introduced by Jones, Lien, and Laaser [34] in 1976: for the membership problem in the Cayley table model the ambient semigroup is given as its full multiplication table (a.k.a. Cayley table), i.e., instead of the finite set Ω as above, the input includes a multiplication table of a semigroup and the elements are given as indices to rows/columns of that multiplication table. Clearly, this is a much less compressed form than the membership problem in the transformation or partial bijection model and, indeed, the membership problem in the Cayley table model is 𝖭𝖫-complete [34].

Like in the transformation model, the case of groups appears to be easier than the general case. Indeed, for certain groups the problem can be solved in 𝖥𝖮𝖫𝖫 as shown by Barrington, Kadau, and Lange [9] and extended to further groups by Collins, Grochow, Levet, and the last author [17]. Moreover, in 1991, Barrington and McKenzie [7] observed that the membership problem for groups in the Cayley table model (which they denote by “gen(groups)” and we by memb(𝐆)𝐂𝐓) can be solved in 𝖫 with an oracle for ugap and speculated about it potentially being 𝖫ugap-complete. They posed the following question.

Does gen(groups) belong to 𝖫? We doubt that this is the case: we believe rather that gen(groups) is complete for the 𝖭𝖢1-closure of ugap, though we do not yet see how to apply the techniques in Cook and McKenzie (1987) to prove that gen(groups) is even 𝖫-hard.

This conjecture has been refuted by the first author of the present article [22, 23] by showing that memb(𝐆)𝐂𝐓 can be solved in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 (at least if we read completeness with respect to 𝖠𝖢0-reductions; when using 𝖭𝖢1-reductions, the results in [22, 23] give only a strong indication that the conjecture does not hold). Yet, in this work, we establish that the conjecture actually holds if we replace groups with inverse semigroups.

To find out in which cases the membership and conjugacy problem are easy and in which cases they are difficult, we study these problems restricted to certain varieties of finite inverse semigroups. A variety of finite (inverse) semigroups, frequently called a pseudovariety, is a class of (inverse) semigroups that is closed under finite direct products, (inverse) subsemigroups, and quotients. Important varieties of finite (inverse) semigroups are groups, semilattices, or aperiodic (inverse) semigroups. Varieties of finite semigroups are closely linked to varieties of formal languages (i.e., classes of languages enjoying natural closure properties) by Eilenberg’s Correspondence Theorem [21].

Beaudry, McKenzie, and Thérien [10] classified the varieties of finite aperiodic monoids in terms of the complexity of their membership problem. They found the following five classes: 𝖠𝖢0, 𝖯-complete, 𝖭𝖯-complete, 𝖭𝖯-hard, and 𝖯𝖲𝖯𝖠𝖢𝖤-complete. Note that it might seem like a negligible difference whether semigroups or monoids are considered; however, the landscape of varieties of finite semigroup is much richer than the varieties of finite monoids. The aim of this work is to provide a similar classification for inverse semigroups.

Our Contribution.

We consider the membership and conjugacy problems for inverse semigroups parametrized by a variety 𝐕. For both problems we are given inverse semigroups US where U is given by generators and U𝐕. Given an element tS, the membership problem asks whether tU. Given elements s,tS, the conjugacy problem asks whether u¯su=t and s=utu¯ for some uU{1}. Both problems are examined with respect to two models of input – the Cayley table model and the partial bijection model. We write memb(𝐕)𝐂𝐓, conj(𝐕)𝐂𝐓, memb(𝐕)𝐏𝐁, and conj(𝐕)𝐏𝐁, accordingly. Regarding further details on the definition we refer to Section 2.4.

Our main result regarding the Cayley table model is the following dichotomy. Herein 𝐂𝐥 denotes the variety of finite Clifford semigroups, which is the smallest variety containing all finite groups and semilattices. The class 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 comprises all problems solvable by non-deterministic random access Turing machines in time log𝒪(1)n; see Section 2.5.

Theorem A (Cayley Table Model).

Let 𝐕 be a variety of finite inverse semigroups.

  • If 𝐕𝐂𝐥, then memb(𝐕)𝐂𝐓 and conj(𝐕)𝐂𝐓 are in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 and in 𝖫.

  • If 𝐕𝐂𝐥, then memb(𝐕)𝐂𝐓 and conj(𝐕)𝐂𝐓 are 𝖫-complete.

In particular, both problems are in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤𝗊𝖠𝖢0 if and only if 𝐕𝐂𝐥 as the class 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 contains no problem that is hard for 𝖫 (with respect to 𝖠𝖢0 reductions). Furthermore, ˜A establishes Barrington and McKenzie’s conjecture [7] on 𝖫ugap-completeness111Recall that 𝖫ugap=𝖫 by Reingold’s seminal result [55]. of the membership problem – however, for the larger class of inverse semigroups or, more specifically, any variety of finite inverse semigroups not contained in 𝐂𝐥.

The condition in ˜A can be equivalently formulated using the following fact. A variety of finite inverse semigroups is contained in 𝐂𝐥 if and only if it does not contain the combinatorial Brandt semigroup B2. The latter consists of elements {s,s¯,ss¯,s¯s,0} where s2=s¯2=0 and all of the other products are as one would expect. Hence, by ˜A, the problems memb(𝐕)𝐂𝐓 and conj(𝐕)𝐂𝐓 are 𝖫-complete if and only if B2𝐕.

We now turn to the partial bijection model. This input model is similar to the transformation model for semigroups considered above – however, the generators and the target elements are partial maps that need to be injective on their domain. Our main result for the partial bijection model is the following dichotomy.

Theorem B (Partial Bijection Model).

Let 𝐕 be a variety of finite inverse semigroups.

  • If 𝐕𝐒𝐈𝐒, then memb(𝐕)𝐏𝐁 is in 𝖭𝖢 and conj(𝐕)𝐏𝐁 is in 𝖭𝖯.

  • If 𝐕𝐒𝐈𝐒, then memb(𝐕)𝐏𝐁 and conj(𝐕)𝐏𝐁 are 𝖯𝖲𝖯𝖠𝖢𝖤-complete.

Herein 𝐒𝐈𝐒 denotes the variety of strict inverse semigroups, which is the smallest variety containing all groups and the combinatorial Brandt semigroup B2; it contains 𝐂𝐥, in particular, all semilattices (denoted as 𝐒𝐥), and the variety generated by B2 (denoted as 𝐁𝐒). As such, B2 no longer serves as a key obstruction to an easy membership problem (as was the case in the Cayley table model). This rôle is now played by the combinatorial Brandt monoid B21. Indeed, a variety of finite inverse semigroups 𝐕 is contained in 𝐒𝐈𝐒 if and only if B21𝐕.

The case 𝐕𝐒𝐈𝐒 in ˜B can be further refined as follows using [10] and our further results (˜A, Lemma 6, Proposition 11 or [4], and Corollary 22).

  • If 𝐕𝐒𝐥, then memb(𝐕)𝐏𝐁 and conj(𝐕)𝐏𝐁 are in 𝖠𝖢0 by [10].

  • If 𝐕=𝐁𝐒, then memb(𝐕)𝐏𝐁 and conj(𝐕)𝐏𝐁 are 𝖫-complete.

  • If 𝐕𝐁𝐒, then memb(𝐕)𝐏𝐁 is in 𝖭𝖢 and conj(𝐕)𝐏𝐁 is in 𝖭𝖯; both are hard for 𝖫.

Note that here 𝖠𝖢0 and 𝖭𝖢 refer to uniform circuit classes and, as such, the three levels of complexity 𝖠𝖢0𝖭𝖢𝖯𝖲𝖯𝖠𝖢𝖤 are separated unconditionally [58, 26]. Therefore, in particular, each of the problems memb(𝐕)𝐏𝐁 and conj(𝐕)𝐏𝐁 is in 𝖠𝖢0 if and only if 𝐕𝐒𝐥, and the problem memb(𝐕)𝐏𝐁 is in 𝖭𝖢 if and only if 𝐕𝐒𝐈𝐒.

For 𝐕𝐒𝐈𝐒 we reduce the problems memb(𝐕)𝐏𝐁 and conj(𝐕)𝐏𝐁 to the corresponding problems for the variety of finite groups, matching their complexity. We build on the celebrated result of Babai, Luks, and Seress [5] which states that the membership problem for permutation groups is in 𝖭𝖢, as well as the observation that, due to groups admitting polylogarithmic SLPs, the corresponding conjugacy problem is in 𝖭𝖯.

As outlined above, membership problems are deeply intertwined with intersection non-emptiness problems for the corresponding classes of automata. In 2016, Bulatov, Kozik, Mayr, and Steindl [13] proved that the intersection non-emptiness problem for DFAs remains 𝖯𝖲𝖯𝖠𝖢𝖤-complete even if the input automata are restricted to at most three states exactly one of which is accepting. This corresponds to semigroups in the transformation model. Here we obtain a similar result for inverse automata, which corresponds to inverse semigroups in the partial bijection model, using the same reduction as for the hardness part of ˜B.

Corollary C.

The intersection non-emptiness problem for inverse automata is 𝖯𝖲𝖯𝖠𝖢𝖤-complete. This holds even if the automata have only two states, one of which is accepting.

The reason that two states suffice to show 𝖯𝖲𝖯𝖠𝖢𝖤-hardness is grounded in the fact that inverse automata have partially defined transition functions, whereas the above-mentioned result concerns automata with total transition functions.

In the same work [13] Bulatov, Kozik, Mayr, and Steindl also considered the subpower membership problem and showed that it is 𝖯𝖲𝖯𝖠𝖢𝖤-complete for arbitrary semigroups. This problem is natural in the context of universal algebra [48, 14, 39, 41] and has been studied for semigroups also in [61, 62]. As a consequence of ˜B and ˜C, we obtain the following dichotomy for the subpower membership problem for inverse semigroups.

Corollary D.

The subpower membership problem for an inverse semigroup S is in 𝖭𝖢 if and only if S𝐒𝐈𝐒. Otherwise, it is 𝖯𝖲𝖯𝖠𝖢𝖤-complete.

Finally, we apply our results to the problems of determining the minimal size of a generating set (mgs) and deciding satisfiability of an equation (eqn) and obtain a similar dichotomy as above. The minimum generating set problem receives as input an inverse semigroup S and an integer k and asks whether S can be generated by at most k elements. For eqn the input is an inverse semigroup S and a single equation, and the question is whether there is a satisfying assignment of the variables to elements of S.

Corollary E.

Let 𝐕 be a variety of finite inverse semigroups.

  • If 𝐕𝐒𝐈𝐒, then mgs(𝐕)𝐏𝐁 and eqn(𝐕)𝐏𝐁 are in 𝖭𝖯.

  • If 𝐕𝐒𝐈𝐒, then mgs(𝐕)𝐏𝐁 and eqn(𝐕)𝐏𝐁 are 𝖯𝖲𝖯𝖠𝖢𝖤-complete.

Due to space constraints most proofs are omitted from this extended abstract. They can be found in the full version of this paper [24] including extended preliminaries and related work. For important results, we provide short proof sketches.

2 Preliminaries and Notation

2.1 Inverse Semigroups

An inverse semigroup is a semigroup S where every xS possesses a unique inverse x¯S, i.e., xx¯x=x and x¯xx¯=x¯ hold and x¯ is the unique element with this property. In an inverse semigroup S all idempotents commute; in particular, its set of idempotents E(S) is a subsemigroup and a semilattice. We denote the natural order on the elements of an inverse semigroup by , i.e., xy if and only if x=xx¯y or, equivalently, x=yx¯x. For an inverse semigroup S and ΣS, we denote by Σ the inverse subsemigroup of S generated by Σ, i.e., the smallest inverse subsemigroup of S containing Σ. The elements of Σ are called generators for Σ. As all elements of Σ can be written as words over ΣΣ¯, we assume from now on that generating sets are closed under formation of inverses, i.e., Σ¯=Σ. Be aware that, unlike in finite groups, arbitrary subsemigroups of an inverse semigroup need not be inverse semigroups again. For further background on (inverse) semigroups see [16, 1, 57, 53, 42].

Symmetric Inverse Semigroups.

The symmetric inverse semigroup (Ω) is the inverse semigroup of all partial bijections on a set Ω, i.e., partial maps s:ΩΩ that induce a bijection from their domain dom(s) to their range ran(s). We write n=({1,,n}).

For s(Ω) and xΩ, we write xs for the image of x under s, where xs= means that xs is undefined. We extend this notation to sets ΔΩ, i.e., Δs={xsxΔ}.

The inverse subsemigroups of (Ω) are sometimes called partial bijection semigroups. An important result by Preston [54] and Wagner [64] states that every inverse semigroup S can be embedded into the symmetric inverse semigroup (S) in a natural way.

The Brandt Semigroup.

The (combinatorial) Brandt semigroup B(Ω) on some set Ω is the inverse subsemigroup {s(Ω)|dom(s)|1} of (Ω). The (combinatorial) Brandt monoid on Ω is the inverse submonoid B1(Ω)=B(Ω){1} of (Ω). We write Bn and Bn1 in case Ω={1,,n}. The Brandt semigroup (or monoid) can be thought of as the complete directed graph on vertices Ω together with an additional zero element (and an identity) where the multiplication of edges (u,v) and (w,z) is (u,z) if v=w and 0 otherwise.

2.2 Green’s Relations and Conjugacy

The following relative variants of Green’s relations will be very useful. As usual, given an inverse semigroup S, we denote by S1 the smallest inverse monoid containing S. However, in a relative context, i.e., for an inverse subsemigroup US, we denote by U1 the inverse submonoid U{1}S1. This abuse of notation is employed in the following definition.

Definition 1.

Let US. Given elements s,tS, we write sUtU1sU1t, sUtsU1tU1, and s𝒥UtU1sU1U1tU1. Furthermore, we write sUt provided that sUt and sUt; the Green’s relations U and 𝒥U are defined similarly. Finally, we let U=UU and 𝒟U=UU.

We recover the usual definition of Green’s relations [28] as 𝒳=𝒳S and 𝒳=𝒳S, where 𝒳{,,𝒥} or 𝒳{,,,𝒟,𝒥}, respectively. Similarly, we will use a relative variant of conjugacy in inverse semigroups defined as follows. Beware that there are other notions of conjugacy frequently considered in the context of semigroup theory; see also [2, 33].

Definition 2.

Let US be inverse semigroups. We call s,tS conjugate relative to U, written sUt, if there exists some uU1 such that u¯su=t and s=utu¯.

Conjugacy and 𝒥-equivalence are closely related for idempotents of inverse semigroups.

Lemma 3.

Let US be inverse semigroups, and let e,eE(S). Then e𝒥Ue holds if and only if e=u¯eu for some uU1. If S is finite, then e𝒥Ue if and only if eUe.

2.3 (Pseudo-)Varieties

A class 𝒞 of finite inverse semigroups is called a variety of finite inverse semigroups (a.k.a. pseudovariety) if it is closed under formation of finite direct products and of divisors (quotients of inverse subsemigroups). By Reiterman’s theorem [56], a variety consists of all finite inverse semigroups that satisfy some set of (pseudo-)identities. Moreover, these classes are closely related to certain classes of formal languages via Eilenberg’s Correspondence Theorem [21].

We will use boldface roman letters to denote varieties of finite inverse semigroups and sometimes also give a set of defining inverse semigroup identities for them. An overview of the varieties of finite inverse semigroups most relevant to our work is given in Figure 1.

Variety Identities Description
𝐓 x=y trivial
𝐈𝐒 inverse semigroups
𝐆 xx¯=yy¯ groups
𝐂𝐥 xx¯=x¯x Clifford semigroups
𝐒𝐈𝐒 y¯xyy¯x¯y=y¯x¯yy¯xy strict inverse semigroups
𝐒𝐥 x2=x semilattices
𝐁𝐒 (y¯xy)2=y¯xy generated by B2
𝐁𝐌 not finitely based [37] generated by B21
𝐀 xω+1=xω aperiodic
Figure 1: Varieties of finite inverse semigroups, their relationships, and defining identities.

The chain 𝐓𝐒𝐥𝐁𝐒𝐁𝐌 forms the bottom of the lattice of the varieties of finite combinatorial (i.e., aperiodic) inverse semigroups. Herein, 𝐁𝐒=(y¯xy)2=y¯xy and 𝐁𝐌 denote the varieties of finite inverse semigroups generated by the (combinatorial) Brandt semigroup B2 and monoid B21, respectively.

Lemma 4 (Kleiman [36, Lemma 4]).

For every finite set Ω, B(Ω)𝐁𝐒 and B1(Ω)𝐁𝐌.

The bottom of the lattice of varieties of finite inverse semigroups is structured as follows.

Proposition 5 (Djadchenko [20], Kleiman [35, 36]; see also [29]).

Let 𝐕 be a variety of finite inverse semigroups. Then 𝐕 is subject to each of the following alternatives.

  1. 1.

    Either 𝐒𝐥𝐕 or 𝐕𝐆=𝐆𝐓.

  2. 2.

    Either 𝐁𝐒𝐕 or 𝐕𝐂𝐥=𝐆𝐒𝐥.

  3. 3.

    Either 𝐁𝐌𝐕 or 𝐕𝐒𝐈𝐒=𝐆𝐁𝐒.

Moreover, the intervals [𝐒𝐥,𝐂𝐥] (or [𝐁𝐒,𝐒𝐈𝐒]) and [𝐓,𝐆] in the lattice of all varieties of finite inverse semigroups are isomorphic via 𝐕𝐕𝐆 and 𝐇𝐇𝐒𝐥 (or 𝐇𝐇𝐁𝐒).

2.4 Algorithmic Problems

The main focus of this work lies on analyzing the algorithmic complexity of two important decision problems for inverse semigroups, and several variants thereof. The first of these problems is the membership problem (memb); it is defined as follows.

Input.Question.

An inverse semigroup S, a subset ΣS, and an element tS.

Question.

Is tU where U=Σ?

The second main decision problem is the conjugacy problem (conj).

Input.Question.

An inverse semigroup S, a subset ΣS, and elements s,tS.

Question.

Is sUt where U=Σ?

As with any decision problem, its algorithmic complexity depends substantially on how its input is given. We consider two input models, the Cayley table model (𝐂𝐓) and the partial bijection model (𝐏𝐁). In the former model, the surrounding inverse semigroup is provided as a complete multiplication table, the so-called Cayley table of S. In the partial bijection model, the surrounding inverse semigroup is the symmetric inverse semigroup n with n provided as part of the input; the elements are given as partial bijections. We denote by membCT and membPB, and by conjCT and conjPB the membership and conjugacy problems in the respective input models. The Preston-Wagner representation [54, 64] of an inverse semigroup is efficiently computable, which leads to the following observation.

Lemma 6.

On input of an inverse semigroup S given as a Cayley table, one can compute an embedding S(S) in 𝖠𝖢0. Hence, membCTm𝖠𝖢0membPB and conjCTm𝖠𝖢0conjPB.

To obtain a detailed analysis of the algorithmic complexity, we impose certain restrictions on the allowed inputs. On the one hand, we consider the idempotent membership and idempotent conjugacy problems where we require that s,tE(S). We denote these variants by E-membIM and E-conjIM where 𝐈𝐌{𝐂𝐓,𝐏𝐁}.

The other kind of restriction we impose is on the structure of the inverse subsemigroup U=Σ under consideration. More specifically, we consider the above problems with U confined to some fixed class 𝐕 of finite inverse semigroups. We call these the (idempotent) membership and conjugacy problem for 𝐕, and denote them by memb(𝐕)𝐈𝐌 and conj(𝐕)𝐈𝐌 where 𝐈𝐌{𝐂𝐓,𝐏𝐁}, respectively. Throughout, the class 𝐕 will be some variety of finite inverse semigroups such as, e.g., the variety 𝐆 of finite groups. Be aware that only U is restricted to the class 𝐕, while S and the elements s,tS can be arbitrary!

We also consider a more restricted variant of the problems, which we denote with a superscript (e.g. memb𝐏𝐁 and conj𝐏𝐁). For these we require in the Cayley table model that S𝐕 and in the partial bijection model that there is some S(Ω) with S𝐕 such that ΣS and tS (resp. s,tS). For the conjugacy problem we also require that sSt. We use these restricted variants to show stronger statements for our hardness results.

2.5 Complexity

For standard complexity classes such as 𝖯𝖲𝖯𝖠𝖢𝖤 or 𝖭𝖯 see any standard textbook [3, 51]. If 𝒞 and 𝒟 are complexity classes, 𝒞𝒟 denotes the class of problems that can be solved in 𝒞 with oracles for a finite set of problems from 𝒟. The circuit class 𝖠𝖢0 consists of the problems decidable by polynomial-size, constant-depth Boolean circuits (where gates may have arbitrary fan-in). Likewise 𝖠𝖢0-computable functions are defined. For a precise definition, we refer to [63]. We write 𝖫 to denote logarithmic space; for many-one reductions computable in logarithmic space we write 𝖫-reductions. When talking about 𝖫-hard problems, throughout we refer to 𝖠𝖢0 many-one reductions.

Let ugap denote the undirected graph accessibility problem. Its input is an undirected graph and two vertices s and t and the question is whether s and t lie in the same connected component. Note that ugap is 𝖫-hard [19]. We crucially rely on the seminal result due to Reingold [55] showing that ugap𝖫 and, hence, 𝖫ugap=𝖫.

The class 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 consists of the problems decidable by non-deterministic random access Turing machines in time log𝒪(1)n. A random access Turing machines has a separate address tape and a query state; whenever the Turing machine goes into the query state and on the address tape the number i is written in binary, the i-th symbol of the input is read (the content of the address tape is not deleted after that). Apart from that, random access Turing machines work like regular Turing machines.

For an overview over the complexity classes we use in this paper and their relationships, see Figure 2. We note that, by [58] and the space hierarchy theorem [60], we have 𝖭𝖢𝖯𝖲𝖯𝖠𝖢𝖤. Moreover, by [17], 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤 can be simulated by circuits of quasipolynomial size and depth two, i.e., 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤𝗊𝖠𝖢0. By [26, 30], 𝗊𝖠𝖢0 does not contain any 𝖫-hard problem as it cannot compute, for instance, parity.

Figure 2: Complexity classes used in this article. (All circuit classes are assumed to be uniform.)

2.6 Straight-Line Programs

Let S be an inverse semigroup and ΣS. A straight-line program (SLP) over Σ is a finite sequence (s1,,sk)Sk such that for all i either siΣ, or si=sjs for some j,<i, or si=sj¯ for some j<i. An SLP as above computes an element sS if s{s1,,sk}.

We say that a class 𝒞 of finite inverse semigroups admits polylogarithmic SLPs if there exists a polynomial P such that, for all S𝒞 and all generating sets ΣS, every element sS is computed by some SLP over Σ of length at most P(log|S|). The analogous property for semigroups and monoids was studied by the first author [23, 22] under the name polylogarithmic circuits property. Using a straight-forward guess-and-check approach, we obtain the following result – for a proof see [22, Corollary 5.2].

Lemma 7 (Fleischer [22, Corollary 5.2]).

Let 𝒞 be a class of finite (inverse) semigroups admitting polylogarithmic SLPs. Then the problem memb(𝒞)𝐂𝐓 is in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤.

3 Membership and Conjugacy in Groups

Groups are a primary example for inverse semigroups. Therefore, let us start exploring some known result and new observations about the membership and conjugacy problems in groups.

In the Cayley table model, deciding the membership and conjugacy problems for groups is comparatively easy. The best currently known approach [18] is based on the non-deterministic computation of a succinct representation of a target element as a product of generators. We pursue a similar idea here and use SLPs for succinct representation. In the case of groups, this approach is afforded by the following Reachability Lemma.

Lemma 8 (Babai, Szemerédi [6, Theorem 3.1]).

The variety 𝐆 of finite groups admits polylogarithmic SLPs. More precisely, for every group G and generating set ΣG, every element of G is computed by an SLP over Σ of length 𝒪(log2|G|).

Guessing and then verifying a representation given by an SLP yields the following complexity bounds. For the first part of the following result, see [22].

Proposition 9.

The problems memb(𝐆)𝐂𝐓 and conj(𝐆)𝐂𝐓 are in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤.

In the partial bijection model, the groups under consideration are permutation groups and it is in this latter setting that the membership and conjugacy problems have been widely studied. However, the problems memb(𝐆)𝐏𝐁 and conj(𝐆)𝐏𝐁 are also subtly different from the corresponding problems for permutation groups simply because the former allow for more possible inputs (partial bijections instead of bijections). In case of the membership problem this distinction is mostly artificial (and can be resolved by appropriate 𝖠𝖢0 reductions).

Proposition 10 (Babai, Luks, and Seress [5]).

The problem memb(𝐆)𝐏𝐁 is in 𝖭𝖢.

We complement the above with the following hardness result.

Proposition 11.

Let 𝐕 be a variety of finite inverse semigroups containing a non-trivial group. Then memb(𝐕)𝐏𝐁 as well as its restricted variant memb(𝐕)𝐏𝐁 are 𝖫-hard.

Note that an even stronger statement holds: solving systems of linear equations modulo a prime p is hard for the logspace counting class 𝖬𝗈𝖽p𝖫 [15] and, in the setting of Proposition 11, this implies hardness for 𝖬𝗈𝖽p𝖫 whenever p divides the order of some group in 𝐕. Moreover, if 𝐕 contains all abelian groups, then memb(𝐕)𝐏𝐁 is hard for the complexity class 𝖬𝗈𝖽𝖫 [4].

The complexity of the conjugacy problem for groups is more intricate. On the one hand, the problem is clearly in 𝖭𝖯 due to the existence of short SLPs (Lemma 8). This observation holds for permutation groups as well as groups in the partial bijection model. On the other hand, the conjugacy problem is 𝖦𝖨-hard for permutation groups, as was observed by Luks [46]. Luks also exhibited several other problems for permutation groups that are polynomial-time equivalent to conjugacy, among which is the set transporter problem.

Input.Question.

A group GPerm(Ω) given by generators, and sets Δs,ΔtΩ.

Question.

Does there exist an element gG such that Δsg=Δt?

The conjugacy problem for permutation groups is clearly a special case of the conjugacy problem for 𝐆 in the partial bijection model, and so is the set transporter problem. In fact, the latter is precisely the idempotent conjugacy problem for 𝐆 (recall that the idempotents of the symmetric inverse semigroup (Ω) are in canonical bijection with the subsets of Ω).

The above discussion can be summarized as follows.

Proposition 12.

Both of the problems conj(𝐆)𝐏𝐁 and E-conj(𝐆)𝐏𝐁 are polynomial-time equivalent to the conjugacy problem for permutation groups; hence, 𝖦𝖨-hard and in 𝖭𝖯.

4 Membership and Conjugacy in Clifford Semigroups

We now turn to Clifford semigroups, which constitute the smallest variety of finite inverse semigroups 𝐂𝐥 to properly contain the variety of finite groups 𝐆. As is the case for groups, every finite Clifford semigroup S admits SLPs of length 𝒪(log2|S|) [22, Lemma 4.10].

Proposition 13.

The problems memb(𝐂𝐥)𝐂𝐓 and conj(𝐂𝐥)𝐂𝐓 are in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤.

Even in the partial bijection model, the complexity of the membership and conjugacy problems for Clifford semigroups is essentially equivalent to those for groups.

Lemma 14.

Let U𝐂𝐥 be generated by Σ(Ω). On input eE((Ω)) and Σ, the minimal idempotent e^E(U){1} such that e^e can be computed in 𝖠𝖢0.

Proposition 15.

If 𝐇𝐆 is a variety of finite groups, then the problems memb(𝐇𝐒𝐥)𝐏𝐁 and conj(𝐇𝐒𝐥)𝐏𝐁 are 𝖠𝖢0-reducible to memb(𝐇)𝐏𝐁 and conj(𝐇)𝐏𝐁, respectively.

Proof.

Let U(Ω) with U𝐇𝐒𝐥 generated by ΣU. In the case of membership, we are given an additional element t(Ω). Using Lemma 14, we compute the minimal idempotent e^E(U){1} with e^tt¯ and verify that e^E(U). Next, we compute the generating set Σe^={e^uuΣ,e^uu¯} of the -class Ue^={uUuu¯=e^}U (which is a group). Then tU if and only if tUe^.

The reduction for the conjugacy problem is similar.

Corollary 16.

The problems memb(𝐂𝐥)𝐏𝐁 and conj(𝐂𝐥)𝐏𝐁 are in 𝖭𝖢 and 𝖭𝖯, respectively.

Choosing 𝐇 as the trivial variety in Proposition 15 yields the result by Beaudry, McKenzie, Thérien [10] that memb(𝐒𝐥)𝐏𝐁 is in 𝖠𝖢0. Furthermore, by Lemma 6, it follows that also memb(𝐒𝐥)𝐂𝐓 is in 𝖠𝖢0. On the other hand, the following question remains open.

Question 17.

Are the problems memb(𝐆)𝐂𝐓 and memb(𝐂𝐥)𝐂𝐓 in 𝖠𝖢0?

5 Membership and Conjugacy in Strict Inverse Semigroups

In this section we show that, in the partial bijection model, the membership and conjugacy problem for 𝐒𝐈𝐒 are 𝖫-reducible to the corresponding problems for 𝐆. In the Cayley table model these problems are 𝖫-complete for 𝐒𝐈𝐒 as we will show in Section 6.

Our reduction is explicit and based on special properties of the representation theory of the variety 𝐒𝐈𝐒. Suppose that U=Σ(Ω) with U𝐒𝐈𝐒. We say that an element uU is Δ-large for some U-invariant subset ΔΩ if its domain dom(u) or, equivalently, its range ran(u) intersects every U-orbit xUΔ. Consider the graph M(Δ;Σ) which, for each Δ-large uΣ, possesses an edge labeled u from a vertex associated with the set Δdom(u)Ω to a vertex associated with the set Δran(u)Ω. This graph, which we call the Munn graph M(Δ;Σ) at Δ and with respect to Σ, is the basis of our reduction. As it turns out, every 𝒟-class of the strict inverse semigroup U is generated (as a groupoid) by a connected component of the Munn graph M(Δ;Σ) at some suitably chosen U-invariant set ΔΣ.

Lemma 18.

Let U(Ω) be as above and let Δ=(dom(e))UΩ for some eE(U). Then the set {fE(U)eUf} is the vertex set of a connected component of M(Δ;Σ).

To decide membership or conjugacy, we identify a suitable set Δ for the 𝒟-class of U containing the potential member or conjugating element, respectively. (E.g., for deciding tU choose Δ=(dom(e^))U where e^E(U){1} is the smallest idempotent with e^tt¯.)

Lemma 19.

Given Σ(Ω) and eE((Ω)) the minimal e^E(U){1} with ee^ can be computed in 𝖫 and, as part of the computation, one can decide whether e^U=Σ.

We then use the Munn graph M(Δ;Σ) to reduce the problem to a suitable -class (i.e., a subgroup) of U (as in the case of Clifford semigroups) including the computation of a generating set. All these computations can be performed in 𝖫ugap, with those involving U-orbits and the Munn graph crucially relying on the graph accessibility problem (ugap). Alluding to Reingold’s seminal result [55] whereby ugap𝖫, we obtain the following.

Theorem 20.

Let 𝐇𝐆 be a variety of finite groups. The problems memb(𝐇𝐁𝐒)𝐏𝐁 and conj(𝐇𝐁𝐒)𝐏𝐁 are 𝖫-reducible to memb(𝐇)𝐏𝐁 and conj(𝐇)𝐏𝐁 for 𝐇, respectively.

Using the facts that memb(𝐆)𝐏𝐁 is in 𝖭𝖢 (by [5], see Proposition 10) and conj(𝐆)𝐏𝐁 is in 𝖭𝖯 (see Proposition 12), this implies the following upper bounds for 𝐒𝐈𝐒=𝐆𝐁𝐒.

Corollary 21.

The problem memb(𝐒𝐈𝐒)𝐏𝐁 is in 𝖭𝖢 and conj(𝐒𝐈𝐒)𝐏𝐁 is in 𝖭𝖯.

The other extreme, i.e., taking 𝐇 to be the trivial variety 𝐓 in Theorem 20, yields the following upper bounds. These are interesting because E-memb(𝐁𝐒)𝐂𝐓 and E-conj(𝐁𝐒)𝐂𝐓 are already complete for 𝖫 as we will later show; see Proposition 26.

Corollary 22.

The problems memb(𝐁𝐒)𝐏𝐁 and conj(𝐁𝐒)𝐏𝐁 are in 𝖫.

6 Inverse Semigroups in the Cayley Table Model

In this section we complete the proof of ˜A. Recall that the variety 𝐂𝐥 of finite Clifford semigroups is the smallest variety containing all groups and semilattices. In Section 4 we have seen that memb(𝐂𝐥)𝐂𝐓 and conj(𝐂𝐥)𝐂𝐓 are in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤. Completing the proof of ˜A consists of two steps. In Proposition 25 we establish 𝖫-algorithms for these problems, and in Proposition 26 we show that the problems are hard for 𝖫 given that 𝐕𝐂𝐥. Before we go into the details of our proof, let us explore an interesting consequence.

Corollary 23.

Let 𝐕 be a variety of finite inverse semigroups. The following are equivalent.

  • The class 𝐕 comprises only Clifford semigroups, i.e., 𝐕𝐂𝐥.

  • The class 𝐕 admits polylogarithmic SLPs.

  • The problem memb(𝐕)𝐂𝐓 is in 𝖭𝖯𝖮𝖫𝖸𝖫𝖮𝖦𝖳𝖨𝖬𝖤.

  • The problem memb(𝐕)𝐂𝐓 is in 𝗊𝖠𝖢0.

Note that the equivalence of the first two points of Corollary 23 can also be proved directly. Indeed, the first author determined in his dissertation [22] the maximal varieties of finite (not necessarily inverse) monoids admitting polylogarithmic SLPs, viz. the varieties of finite Clifford monoids and of finite commutative monoids. However, the situation for semigroups is considerably more intricate. Therefore, we point out the following open problem.

Question 24.

Which varieties of arbitrary finite semigroups admit polylogarithmic SLPs?

The membership problem for semigroups in the Cayley table model belongs to 𝖭𝖫 [34]. Here we go even further and show that this can improved to 𝖫 for inverse semigroups. Recall that 𝖭𝖫 is intricately related to directed graph accessibility, while 𝖲𝖫 = 𝖫 by Reingold’s result [55] corresponds to undirected graph accessibility.

Proposition 25.

The problems membCT and conjCT are is in 𝖫.

Proof Sketch.

The problem conjCT is essentially reachability in an undirected graph. To decide whether or not sΣt, consider the graph with vertex set S and edges {x,y} whenever there is some uΣ such that u¯xu=y and x=uyu¯. Now, sΣt if and only if s and t are in the same connected component. The latter is an instance of ugap, which by Reingold’s result [55] can be solved in 𝖫. For membCT, consider as intermediate step the problem of deciding whether sUt for elements s,tS. Using the same approach as above, this can be decided in 𝖫. Now, to decide membCT, we use the following algorithm, where we assume without loss of generality that S is a monoid and U is a submonoid.

Note that throughout, we keep the invariants that xU and xx¯t=t (i.e., xt). Therefore, if our algorithm outputs true, then, indeed, tU. Moreover, the condition yuu¯y in line 2 implies that y>Uyu. Hence, the algorithm always terminates. Now, if tU and x>Ut, the algorithm will repeatedly find y and u meeting the conditions in line 2 until it eventually terminates with output true.

We now turn to hardness results for the (idempotent) membership and conjugacy problems for inverse semigroups in the Cayley table model. Recall that a variety of finite inverse semigroups 𝐕 satisfies 𝐕𝐂𝐥 if and only if 𝐁𝐒𝐕. The proof of the following proposition is by a direct reduction from ugap. Given a graph G=(V,E), consider the Brandt semigroup B(V), which by Lemma 4 is contained in 𝐁𝐒. For x,yV, there is a unique element mapping x to y, which can be used to encode an edge xy of G. This leads to the following result.

Proposition 26.

Let 𝐕 be a variety of finite inverse semigroups and suppose that 𝐁𝐒𝐕. Then the problems E-conj(𝐕)𝐂𝐓 and E-memb(𝐕)𝐂𝐓 are 𝖫-hard under 𝖠𝖢0-reductions.

7 Inverse Semigroups in the Partial Bijection Model

In this section we finally complete the proof of our dichotomy ˜B regarding the membership and conjugacy problem for inverse semigroups in the partial bijection model. Recall that either 𝐕𝐒𝐈𝐒 or 𝐁𝐌𝐕 for each variety 𝐕 of finite inverse semigroups by Proposition 5. With the first part of ˜B covered by Corollary 21, it suffices to show that the problems memb(𝐁𝐌)𝐏𝐁 and conj(𝐁𝐌)𝐏𝐁 are 𝖯𝖲𝖯𝖠𝖢𝖤-complete. Moreover, since these problems are clearly contained in 𝖯𝖲𝖯𝖠𝖢𝖤, it remains to prove their hardness.

Theorem 27.

The problems E-memb(𝐁𝐌)𝐏𝐁 and E-conj(𝐁𝐌)𝐏𝐁 are 𝖯𝖲𝖯𝖠𝖢𝖤-complete.

We prove 𝖯𝖲𝖯𝖠𝖢𝖤-hardness by a reduction from the decision problem ncl of non-determinstic constraint logic (NCL), which was introduced by Hearn and Demaine [31] and which we briefly describe in the following.

An NCL machine Γ is an edge-weighted simple undirected graph, every vertex of which has degree three, and every edge of which has weight one or two. A configuration of the NCL machine is an orientation of all edges such that the sum of the incoming edge weights (in-flow) at every vertex is at least two. We will denote the set of all configurations by 𝒞(Γ). Two configurations are related by a transition if they differ in the orientation of a single edge.

The decision problem ncl, in the configuration-to-configuration variant, is given as follows.

Input.Question.

An NCL machine Γ, and two configurations Cs,Ct𝒞(Γ).

Question.

Are Cs and Ct related by a sequence of transitions?

This problem is essentially a compressed version of the accessibility problem for undirected graphs, where accessibility is decided on the implicitly given graph of configurations and transitions between these. The problem ncl is complete for 𝖯𝖲𝖯𝖠𝖢𝖤 [31, Theorem 5].

Crucially, the validity of any configuration of an NCL machine Γ can be verified locally, as the minimum in-flow constraint has to be satisfied at each vertex individually. We call an orientation of all edges incident with a fixed vertex v a local configuration at v provided that the minimum in-flow constraint at v is satisfied. The set of all local configurations at v will be denoted by 𝒞(Γ,v) and the corresponding restriction of C𝒞(Γ) by C|v𝒞(Γ,v).

Proof Sketch for Theorem 27.

We only sketch the reduction from ncl to E-conj(𝐁𝐌)𝐏𝐁 since 𝐒𝐥𝐁𝐌 and, in general, E-conj(𝐕)𝐏𝐁 efficiently reduces to E-memb(𝐕𝐒𝐥)𝐏𝐁.

Given Γ, we associate to it the inverse semigroup SΓ=vV(Γ)B1(𝒞(Γ,v)). Every configuration C𝒞(Γ) has an idempotent e(C)E(SΓ) canonically associated to; the projection of e(C) onto B1(𝒞(Γ,v)) is given by the idempotent at C|v𝒞(Γ,v). Any two such idempotents e(C), e(C) are conjugate in SΓ. In a similar way, we encode the transitions of Γ as elements of SΓ. More precisely, we consider elements acting (via conjugation) as a transition would in those two components B1(𝒞(Γ,v)) where v is incident with the reversed edge; and with projections to all other components being trivial, i.e., equal to 1B1(𝒞(Γ,v)).

Given Cs,Ct𝒞(Γ), let UΓSΓ be the inverse subsemigroup generated by e(Cs), e(Ct), and all encoded transitions of Γ. Then the idempotents e(Cs) and e(Ct) are conjugate in UΓ if and only if Cs and Ct are related by a sequence of transitions of Γ.

Let us now consider a variation of the above reduction for the intersection non-emptiness problem for inverse automata. An inverse automaton (IA) is a deterministic finite automation222For a definition we refer the reader to standard textbooks (e.g., [32]). (DFA) 𝒜=(Q,Σ,δ,q0,F) with a partially defined transition function δ:Q×ΣQ such that the following conditions are satisfied.

  • For each aΣ, the partial map δa:QQ with qδ(q,a) is injective on its domain.

  • For each aΣ, there is a word waΣ such that δaδwa is the identity on dom(δa), where δwa=δa1δa2δan is the partial map induced by wa=a1a2an.333We view the maps δa as elements of (Q) and, as such, compose them as operators acting on the right.

 Remark 28.

We will only encounter inverse automata over some alphabet endowed with an involution aa¯ where one can take wa=a¯ in the second condition above.

The intersection non-emptiness problem for a class 𝒳 of automata (e.g., 𝒳=dfa or 𝒳=ia), which we denote by 𝒳-int-empty, is the decision problem defined as follows.

Input.Question.

Automata 𝒜1,,𝒜k𝒳.

Question.

Is L=i=1k(𝒜i) non-empty?

The problems dfa-int-empty and ia-int-empty are 𝖯𝖲𝖯𝖠𝖢𝖤-complete; see [40] and [11], respectively. We sketch a short proof of these results based on the reduction from ncl.

Theorem 29 (˜C).

The problem ia-int-empty is complete for 𝖯𝖲𝖯𝖠𝖢𝖤. Moreover, this holds under the restriction that each automaton provided as part of the input has only two states, one of which is accepting.

Proof Sketch.

Given an NCL machine Γ, we consider the set 𝒬(Γ)=v𝒞(Γ,v). Using a one-hot encoding, we embed 𝒞(Γ,v) into the states of |𝒞(Γ,v)| many two-state inverse automata. As such, 𝒬(Γ)=v𝒞(Γ,v) embeds into the states of v|𝒞(Γ,v)| many two-state inverse automata. The initial states of the automata correspond to (Cs|v)v𝒬(Γ) and the accepting states to (Ct|v)v𝒬(Γ) for some Cs,Ct𝒞(Γ). The common alphabet is then used to encode the local effects of the transitions of Γ as in the proof of Theorem 27.

The intersection of the languages accepted by the automata constructed in this way contains precisely the sequences of transitions of Γ transforming Cs into Ct.

Every inverse automaton can be transformed into a complete DFA be introducing one additional state (and transitions to it). As such, Theorem 29 entails the following result of Bulatov, Kozik, Mayr, and Steindl [13]: dfa-int-empty is complete for 𝖯𝖲𝖯𝖠𝖢𝖤 even if each automaton provided as part of the input has only three states, one of which is accepting.

Next, we derive a corresponding dichotomy result for the subpower membership problem of an inverse semigroup S. This problem is defined as follows.444The inverse semigroup S is treated as a constant and is not part of the input.

Input.Question.

An integer k, a subset ΣSk, and an element tSk.

Question.

Is tU where U=Σ?

This problem can be seen as a special case of membPB, which, by ˜B implies that it can be solved in 𝖯𝖲𝖯𝖠𝖢𝖤 and, if S𝐒𝐈𝐒, even in 𝖭𝖢. From Theorem 29, it follows easily that the subpower membership problem for B21 is 𝖯𝖲𝖯𝖠𝖢𝖤-hard (e.g. using the same argument as [33, Theorem 4.10]). We can build upon this observation and show the following.

Corollary 30 (˜D).

The subpower membership problem of an inverse semigroup S is complete for 𝖯𝖲𝖯𝖠𝖢𝖤 if and only if the Brandt monoid B21 divides S; otherwise, it is in 𝖭𝖢.

8 Further Related Problems

Finally, let us explore the consequences of our results to the minimum generating set problem and the problem of solving equations. The minimum generating set problem has first been considered by Papadimitriou and Yannahakis [52] and, in the Cayley table model, recently shown to be in 𝖯 by Lucchini and Thakkar [44] and even 𝖭𝖢 by Collins, Grochow, Levet, and the last author [17]. Yet, the complexity for arbitrary semigroups and also for permutation groups remains wide open. The minimum generating set problem (mgs) is defined as follows.

Input.Question.

An inverse semigroup U and an integer k.

Question.

Is there some ΞU with |Ξ|k and Ξ=U?

Like for the membership problem, we write mgsPB if U is given as generators for an inverse subsemigroup of n and denote the restriction to a variety 𝐕 by mgs(𝐕)𝐏𝐁. The crucial connection to the membership problem is as follows.

Lemma 31.

Let 𝐕 be a variety of finite inverse semigroups. Then the restricted membership problem memb(𝐕)𝐏𝐁 is 𝖠𝖢0-many-one-reducible to the problem mgs(𝐕𝐒𝐥)𝐏𝐁.

Together with the observation that mgs(𝐕)𝐏𝐁 can be solved in 𝖭𝖯memb(𝐕)𝐏𝐁 and the hardness result Theorem 27, this gives the proof of the first part of ˜E.

Next, let us consider the problem of deciding satisfiability of equations. Let 𝒳 be a set of variables. An equation =r in an inverse semigroup S is given as non-empty words ,r(S𝒳𝒳¯)+. An assignment is a map σ:𝒳S, which naturally extends to a homomorphism from σ:(S𝒳𝒳¯)+S. The problem eqn of deciding whether a system of equations has a solution is defined as follows.

Input.Question.

An inverse semigroup S, and words 1,r1,,k,rk(S𝒳𝒳¯)+.

Question.

Is there a σ:𝒳S such that σ(i)=σ(ri) for all 1ik?

We denote this problem in the Cayley table model and partial bijection model by eqn𝐂𝐓 and eqn𝐏𝐁, respectively. The problem of deciding whether a single equation has a solution occurs as a special case when k=1, denoted by eqnCT and eqnPB. Our key lemma on equations is that the 𝖯𝖲𝖯𝖠𝖢𝖤-hardness of E-conj(𝐁𝐌)𝐏𝐁 can be transferred to eqnPB.

Lemma 32.

The problem eqn(𝐕)𝐏𝐁 is hard for 𝖯𝖲𝖯𝖠𝖢𝖤 whenever 𝐕𝐒𝐈𝐒.

As for mgs, we observe that eqn(𝐕)𝐏𝐁 is solvable in 𝖭𝖯 with an oracle for memb(𝐕)𝐏𝐁. Thus, by Lemma 32, the problems eqn(𝐕)𝐏𝐁 and eqn(𝐕)𝐏𝐁 are in 𝖭𝖯 if 𝐕𝐒𝐈𝐒 and 𝖯𝖲𝖯𝖠𝖢𝖤-complete otherwise, which constitutes the second part of ˜E.

In addition, the problems of deciding whether a single equation or a system of equations have a solution are known to be 𝖭𝖯-hard for many fixed inverse semigroups. Indeed, based on [27], [8, Theorem 6], and [38] we obtain the following refined statement, where 𝐕 is a variety of finite inverse semigroups. Here 𝐆sol denotes the variety of finite solvable groups and 𝐂𝐨𝐦=𝐀𝐛𝐒𝐥 the variety of finite commutative inverse semigroups.

  • The problem eqn(𝐕)𝐏𝐁 is 𝖯𝖲𝖯𝖠𝖢𝖤-complete whenever 𝐕𝐒𝐈𝐒.

  • The problems eqn(𝐕)𝐂𝐓 and eqn(𝐕)𝐏𝐁 are 𝖭𝖯-hard whenever 𝐕𝐆sol𝐁𝐒.

  • The problems eqn(𝐕)𝐂𝐓 and eqn(𝐕)𝐏𝐁 are 𝖭𝖯-hard whenever 𝐕𝐂𝐨𝐦.

9 Discussion and Open Problems

By investigating the membership problem in inverse semigroups, we filled a gap between the rather restricted case of groups and the very general case of arbitrary semigroups. We gave a classification of the complexity of membership and conjugacy in inverse semigroups according to their combinatorial structure. Here the combinatorial Brandt semigroup and monoid are the critical obstructions for the membership problem being easy. Furthermore, by applying these results, we gained new insights on the complexity of closely related problems such as the intersection non-emptiness problem for inverse automata, the minimum generating set problem, and the equation satisfiability problem.

Applying ˜A and ˜B to the case of aperiodic inverse semigroups shows that the membership and conjugacy problems are either in 𝖠𝖢0, or 𝖫-complete, or 𝖯𝖲𝖯𝖠𝖢𝖤-complete (with 𝖯𝖲𝖯𝖠𝖢𝖤-complete only in the partial bijection model). Thus, in comparison to the classification for varieties of aperiodic monoids [10], we additionally have the 𝖫-complete case, whereas we do not have the 𝖯-complete, 𝖭𝖯-complete, and 𝖭𝖯-hard cases.

A corresponding classification of the complexity of the membership problem for varieties of arbitrary semigroups is still a major endeavor. While there is the classification for aperiodic monoids by Beaudry, McKenzie, and Thérien [10] mentioned above, the case for semigroups is considerably more involved as there are many more varieties of finite semigroups than of finite monoids. Moreover, it remains to integrate the case of groups into the consideration.

Open Problem 33.

Give a classification of the varieties of finite semigroups in terms of their complexity for the membership problem.

Another class of structures, situated between inverse semigroups and arbitrary semigroups, that we would like to draw attention to is the class of regular -semigroups introduced by Nordahl and Scheiblich [50]. These are regular semigroups with distinguished inverses xx such that x=x, (xy)=yx, and xxx=x. The difference to inverse semigroups is that inverses need not be unique or, equivalently, that idempotents need not commute. As such, regular -semigroups admit a far richer combinatorial structure.

Open Problem 34.

Give a classification of the varieties of finite regular -semigroups in terms of their complexity for the membership problem.

Our algorithms for the 𝖭𝖢 (resp. 𝖭𝖯) cases of our dichotomy result for the partial bijection model are very efficient in the sense that they provide reductions computable in 𝖫 and also in linear or quadratic time to ugap as well as to the respective problems for groups. Thus, the only open questions about the complexity of these problems come from the group case. Here, for the membership problem we have the results that memb(𝐆)𝐏𝐁 is in 𝖭𝖢 [5] (see Proposition 10) and hard for the logspace counting class 𝖬𝗈𝖽𝖫 [4] (see Proposition 11). This leads to the following question.

Question 35.

What is the precise complexity of memb(𝐆)𝐏𝐁?

We do not feel confident to make any guess about this question and want to use the present work to foster further research on this topic. On the other hand, we believe that the answer to the following question concerning the Cayley table model is likely to be negative.

Question 36.

Is memb(𝐆)𝐂𝐓 in 𝖠𝖢0?

Another question is whether the 𝒪(log2n) bound due to Babai and Szemerédi [6] on the length of straight-line programs in groups of order n is asymptotically optimal. In some special cases, like for Abelian groups, an (asymptotically optimal) 𝒪(logn) bound can be obtained instead. Thus, the question here is whether this can be extended to all groups.

For inverse semigroups, we obtained a complete characterization of varieties admitting polylogarithmic SLPs in Corollary 23. A similar result for monoids was obtained by the first author [22]. Therefore, the natural question is to ask for a similar characterization for all semigroups. For some preliminary results in that direction, see also [22].

References

  • [1] J. Almeida. Finite Semigroups and Universal Algebra. World Scientific, Singapore, 1994.
  • [2] J. Araújo, M. Kinyon, and J. Konieczny. Conjugacy in inverse semigroups. J. Algebra, 533:142–173, 2019. doi:10.1016/j.jalgebra.2019.05.022.
  • [3] S. Arora and B. Barak. Computational Complexity – A Modern Approach. Cambridge University Press, 2009.
  • [4] V. Arvind and T. C. Vijayaraghavan. Abelian permutation group problems and logspace counting classes. In CCC 2004, Proceedings, pages 204–214. IEEE Computer Society, 2004. doi:10.1109/CCC.2004.1313844.
  • [5] L. Babai, E. M. Luks, and Á Seress. Permutation groups in NC. In STOC 1987, Proceedings, STOC ’87, pages 409–420, 1987. doi:10.1145/28395.28439.
  • [6] L. Babai and E. Szemerédi. On the complexity of matrix group problems I. In FOCS 1984, Proceedings, pages 229–240, October 1984. doi:10.1109/SFCS.1984.715919.
  • [7] D. A. M. Barrington and P. McKenzie. Oracle branching programs and Logspace versus P. Information and Computation, 95(1):96–115, 1991. doi:10.1016/0890-5401(91)90017-V.
  • [8] D. A. M. Barrington, P. McKenzie, C. Moore, P. Tesson, and D. Thérien. Equation satisfiability and program satisfiability for finite monoids. In MFCS 2000, Proceedings, volume 1893 of Lecture Notes in Computer Science, pages 172–181. Springer, 2000. doi:10.1007/3-540-44612-5_13.
  • [9] D. M. Barrington, P. Kadau, K. Lange, and P. McKenzie. On the complexity of some problems on groups input as multiplication tables. Journal of Computer and System Sciences, 63(2):186–200, 2001. doi:10.1006/jcss.2001.1764.
  • [10] M. Beaudry, P. McKenzie, and D. Thérien. The membership problem in aperiodic transformation monoids. J. ACM, 39(3):599–616, 1992. doi:10.1145/146637.146661.
  • [11] J.-C. Birget, S. Margolis, J. Meakin, and P. Weil. PSPACE-completeness of certain algorithmic problems on the subgroups of free groups. In ICALP 1994, Proceedings, volume 820 of Lecture Notes in Computer Science, pages 274–285, Berlin, 1994. Springer. Journal version in Theoretical Computer Science, 242:247–281, 2000. doi:10.1007/3-540-58201-0_75.
  • [12] M. Blondin, A. Krebs, and P. McKenzie. The complexity of intersecting finite automata having few final states. Electron. Colloquium Comput. Complex., TR12-090, 2012. URL: https://eccc.weizmann.ac.il/report/2012/090.
  • [13] A. Bulatov, M. Kozik, P. Mayr, and M. Steindl. The subpower membership problem for semigroups. Int. J. Algebra Comput., 26(7):1435–1451, 2016. doi:10.1142/S0218196716500612.
  • [14] A. Bulatov, P. Mayr, and Á. Szendrei. The subpower membership problem for finite algebras with cube terms. Log. Methods Comput. Sci., 15(1), 2019. doi:10.23638/LMCS-15(1:11)2019.
  • [15] G. Buntrock, C. Damm, U. Hertrampf, and C. Meinel. Structure and importance of logspace-MOD class. Math. Syst. Theory, 25(3):223–237, 1992. doi:10.1007/BF01374526.
  • [16] A. H. Clifford and G. B. Preston. The algebraic theory of semigroups, volume 1,2. American Mathematical Society, 1961,1967.
  • [17] N. A. Collins, J. A. Grochow, M. Levet, and A. Weiß. Constant depth circuit complexity for generating quasigroups. In ISSAC 2024, Proceedings, pages 198–207. ACM, 2024. doi:10.1145/3666000.3669691.
  • [18] N. A. Collins, J. A. Grochow, M. Levet, and A. Weiß. On the constant-depth circuit complexity of generating quasigroups. CoRR, abs/2402.00133, 2024. doi:10.48550/arXiv.2402.00133.
  • [19] S. A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. Journal of Algorithms, 8(3):385–394, 1987. doi:10.1016/0196-6774(87)90018-6.
  • [20] G. G. Djadchenko. On identities in monogenic inverse semigroups. Algebra and Theory of Numbers, Nalčik, 2:57–77, 1977.
  • [21] S. Eilenberg. Automata, Languages, and Machines, volume B. Academic Press, New York and London, 1976.
  • [22] L. Fleischer. Algorithms and complexity results for finite semigroups. Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2019. doi:10.18419/opus-10339.
  • [23] L. Fleischer. The Cayley semigroup membership problem. Theory Comput., 18:1–18, 2022. doi:10.4086/toc.2022.v018a008.
  • [24] L. Fleischer, F. Stober, A. Thumm, and A. Weiß. Membership and conjugacy in inverse semigroups. CoRR, abs/2502.10103, 2025. doi:10.48550/arXiv.2502.10103.
  • [25] M. Furst, J. Hopcroft, and E. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pages 36–41, October 1980. doi:10.1109/SFCS.1980.34.
  • [26] M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. doi:10.1007/BF01744431.
  • [27] M. Goldmann and A. Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002. doi:10.1006/inco.2002.3173.
  • [28] J. A. Green. On the structure of semigroups. Ann. Math. (2), 54:163–172, 1951.
  • [29] T. E. Hall and K. G. Johnston. The lattice of pseudovarieties of inverse semigroups. Pacific J. Math., 138(1):73–88, 1989. URL: http://projecteuclid.org/euclid.pjm/1102650281.
  • [30] J. Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, pages 6–20, New York, NY, USA, 1986. ACM. doi:10.1145/12130.12132.
  • [31] R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoret. Comput. Sci., 343(1-2):72–96, 2005. doi:10.1016/j.tcs.2005.05.008.
  • [32] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
  • [33] T. Jack. On the complexity of inverse semigroup conjugacy. Semigroup Forum, 106(3):618–632, 2023. doi:10.1007/s00233-023-10349-y.
  • [34] N. D. Jones, Y. E. Lien, and W. T. Laaser. New problems complete for nondeterministic log space. Mathematical Systems Theory, 10(1):1–17, December 1976. doi:10.1007/BF01683259.
  • [35] E. I. Kleiman. The lattice of varieties of inverse semigroups. Ivz. Vysš. Učbn. Zaved. Mat., 7:106–109, 1976.
  • [36] E. I. Kleiman. On basis of identities of Brandt semigroups. Semigroup Forum, 13:209–218, 1977.
  • [37] E. I. Kleiman. Bases of identities of varieties of inverse semigroups. Sib. Math. J., 20(4):530–543, 1979. doi:10.1007/BF00970367.
  • [38] O. Klíma, P. Tesson, and D. Thérien. Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst., 40(3):263–297, 2007. doi:10.1007/s00224-005-1279-2.
  • [39] M. Kompatscher. The subpower membership problem of 2-nilpotent algebras. In STACS 2024, Proceedings, volume 289 of LIPIcs, pages 46:1–46:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.STACS.2024.46.
  • [40] D. Kozen. Lower bounds for natural proof systems. In Proc. of the 18th Ann. Symp. on Foundations of Computer Science, FOCS’77, pages 254–266, Providence, Rhode Island, 1977. IEEE Computer Society Press.
  • [41] M. Kozik. A finite set of functions with an EXPTIME-complete composition problem. Theor. Comput. Sci., 407(1-3):330–341, 2008. doi:10.1016/J.TCS.2008.06.057.
  • [42] M. V. Lawson. Inverse Semigroups: The Theory of Partial Symmetries. World Scientific, 1999.
  • [43] H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoret. Comput. Sci., 19(2):161–187, 1982. doi:10.1016/0304-3975(82)90058-5.
  • [44] A. Lucchini and D. Thakkar. The minimum generating set problem. Journal of Algebra, 640:117–128, 2024. doi:10.1016/j.jalgebra.2023.11.012.
  • [45] E. M. Luks. Parallel algorithms for permutation groups and graph isomorphism. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 292–302. IEEE Computer Society, 1986. doi:10.1109/SFCS.1986.39.
  • [46] E. M. Luks. Permutation Groups and Polynomial-Time Computation. In Groups and computation (New Brunswick, NJ, 1991), volume 11 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 139–175. Amer. Math. Soc., Providence, RI, 1993. doi:10.1090/dimacs/011/11.
  • [47] E. M. Luks and P. McKenzie. Parallel algorithms for solvable permutation groups. J. Comput. Syst. Sci., 37(1):39–62, 1988. doi:10.1016/0022-0000(88)90044-X.
  • [48] P. Mayr. The subpower membership problem for Mal’cev algebras. Int. J. Algebra Comput., 22(7), 2012. doi:10.1142/S0218196712500750.
  • [49] P. McKenzie and S. A. Cook. The parallel complexity of abelian permutation group problems. SIAM J. Comput., 16(5):880–909, October 1987. doi:10.1137/0216058.
  • [50] T. E. Nordahl and H. E. Scheiblich. Regular * semigroups. Semigroup Forum, 16:369–378, 1978. doi:10.1007/BF02194636.
  • [51] C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
  • [52] C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci., 53(2):161–170, 1996. doi:10.1006/JCSS.1996.0058.
  • [53] M. Petrich. Inverse semigroups. Pure Appl. Math. (N. Y.). John Wiley & Sons, Inc., New York, 1984.
  • [54] G. B. Preston. Representations of Inverse Semi-Groups. J. Lond. Math. Soc. (1), 29(4):411–419, 1954. doi:10.1112/jlms/s1-29.4.411.
  • [55] O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, September 2008. doi:10.1145/1391289.1391291.
  • [56] J. Reiterman. The Birkhoff theorem for finite algebras. Algebra Univers., 14:1–10, 1982.
  • [57] J. L. Rhodes and B. Steinberg. The 𝔮-theory of finite semigroups. Springer Monographs in Mathematics. Springer, 2009.
  • [58] W. L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci., 22(3):365–383, 1981. doi:10.1016/0022-0000(81)90038-6.
  • [59] C. C. Sims. Computational methods in the study of permutation groups. In Proceedings of the Conference on Computational Problems in Abstract Algebra 1967, Oxford, United Kingdom, pages 169–183, New York, 1970. Pergamon. doi:10.1016/B978-0-08-012975-4.50020-5.
  • [60] R. E. Stearns, J. Hartmanis, and P. Lewis II. Hierarchies of memory limited computations. In SWCT 1965, Proceedings, pages 179–190. IEEE Computer Society, 1965. doi:10.1109/FOCS.1965.11.
  • [61] M. Steindl. The subpower membership problem for bands. J. Algebra, 489:529–551, 2017. doi:10.1016/j.jalgebra.2017.06.034.
  • [62] M. Steindl. On semigroups with PSPACE-complete subpower membership problem. J. Aust. Math. Soc., 106(1):127–142, 2019. doi:10.1017/S1446788718000010.
  • [63] H. Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. doi:10.1007/978-3-662-03927-4.
  • [64] V. V. Wagner. Generalised groups. Dokl. Akad. Nauk SSSR, 84(6):1119–1122, 1952.