The membership problem for algebraic structures asks whether a given element belongs to a specific substructure, typically defined by a set of generators. For finite semigroups this problem has been shown to be PSPACE-complete in the transformation model (Kozen, 1977) and NL-complete in the Cayley table model (Jones, Lien, and Laaser, 1976). More recently, the membership and conjugacy problems for finite inverse semigroups were also found to be PSPACE-complete in the partial bijection model (Jack, 2023). In contrast, the membership problem for permutation groups, as established in the seminal work of Babai, Luks, and Seress (1987), is significantly less complex and falls within NC.

In this talk, I will present new results on the complexity of the membership and conjugacy problems for finite inverse semigroups parametrized by varieties of such. The main results are two new dichotomy theorems that classify the complexity of these problems in the partial bijection model and the Cayley table model. Additionally, I will discuss implications for related problems, such as the intersection non-emptiness problem for inverse automata.