11
$\begingroup$

Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.

$\endgroup$
  • $\begingroup$ Are there any specific reason to consider inverse semigroups? What is known about the complexity of the finite group isomorphism problem and the finite semigroup isomorphism problem? $\endgroup$ – J.-E. Pin Jan 8 '15 at 15:13
  • 1
    $\begingroup$ @J.-E.Pin The finite semigroup isomorphism problem is GI-complete, the finite group isomorphism problem is not known to be GI-complete. The wikipedia article linked in the question states that isomorphism of "commutative class 3 nilpotent (i.e., $xyz=0$ for every elements $x,y,z$) semigroups" is GI-complete. $\endgroup$ – Thomas Klimpel Jan 8 '15 at 16:15
  • 1
    $\begingroup$ Commutative class 3 nilpotent semigroups are not embeddable into inverse semigroups, according to an old result by B. Schein, cited by Mark Sapir here. (I read a bit in the cited paper, but haven't worked through it thoroughly "yet", maybe I should.) $\endgroup$ – Thomas Klimpel Jan 9 '15 at 9:35
9
$\begingroup$

Yes, the finite inverse semigroup isomorphism problem is GI-complete! This is a corollary of

Theorem: Lattice isomorphism is isomorphism complete

from section 7.2 Lattices and Posets in

Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.

because a (semi-)lattice is also an (idempotent commutative) inverse semigroup.

Proof of theorem from technical report:

It suffices to represent a graph uniquely as a lattice. Given a graph $G$ with $n$ vertices and $m$ edges, we define a lattice with an element for each vertex, an element for each edge, and two additional elements $\text{'}0\text{'}$ and $\text{'}1\text{'}$. Element $\text{'}1\text{'}$ dominates all others (the supremum), and element $\text{'}0\text{'}$ is dominated by all other elements (the infimum). An edge dominates exactly those vertices which are its endpoints. The result is a lattice which uniquely represents $G$.


The idea for this answer came from a discussion with vzn about sufficiently focused questions. The motivation to spend time on graph isomorphism at all also came from vzn's repeated prodding. J.-E. Pin asked in the comment whether there are any specific reasons to consider inverse semigroups. The idea was to have a structure slightly generalizing groups, which is GI complete. I wanted to better understand the relation between group isomorphism and graph isomorphism, but I fear this answer doesn't provide any insight of this sort.

$\endgroup$
  • 2
    $\begingroup$ Somewhat confusingly, there's also this lattice isomorphism problem which is GI-hard but not known to be GI-complete: www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf $\endgroup$ – Huck Bennett Jul 16 '15 at 2:53
  • 1
    $\begingroup$ @HuckBennett Are you really confused, or would you just like to hear my opinion on lattice theory? The name "lattice" is simply unlucky: "G. Birkhoff also introduced the English word “lattice”, which is not the translation of its German equivalent, but was inspired by the image of some Hasse diagrams presenting lattices." The bad reputation of lattice theory might have been avoided by splitting it into algebraic logic, formal concept analysis, and order theory. $\endgroup$ – Thomas Klimpel Jul 16 '15 at 8:36
  • 1
    $\begingroup$ "Are you really confused, or would you just like to hear my opinion on lattice theory?" Neither, actually. I thought someone in addition to me may have been familiar with that definition of lattice isomorphism and not this one, and that the link might help. $\endgroup$ – Huck Bennett Jul 16 '15 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.