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

<blockquote>
  <p><strong>Theorem:</strong> Lattice isomorphism is isomorphism complete</p>
</blockquote>

<p>from section 7.2 Lattices and Posets in</p>

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

<p>because a (semi-)lattice is also an (idempotent commutative) inverse semigroup.</p>

<p>Proof of theorem from technical report:</p>

<blockquote>
  <p>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 <em>supremum</em>), and element $\text{'}0\text{'}$ is dominated by all other elements (the <em>infimum</em>). An edge dominates exactly those vertices which are its endpoints. The result is a lattice which uniquely represents $G$.</p>
</blockquote>

<hr>

<p>The idea for this answer came from a <a href="http://chat.stackexchange.com/transcript/message/22783789#22783789">discussion with vzn about sufficiently focused questions</a>. 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 <a href="https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/">group isomorphism</a> and graph isomorphism, but I fear this answer doesn't provide any insight of this sort.</p>

CC BY-SA 3.0
2015-07-16T02:53:49.030Z
Somewhat confusingly, there's also this lattice isomorphism problem which is GI-hard but not known to be GI-complete: http://www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf
Huck Bennett
CC BY-SA 3.0
2015-07-16T08:36:05.233Z
@HuckBennett Are you really confused, or would you just like to hear my opinion on lattice theory? The name "lattice" is [simply unlucky](http://dml.cz/bitstream/handle/10338.dmlcz/401261/DejinyMat_17-2001-1_31.pdf): "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](http://dpt-info.u-strasbg.fr/~cronse/lt.html) might have been avoided by splitting it into algebraic logic, formal concept analysis, and order theory.
Thomas Klimpel
CC BY-SA 3.0
2015-07-16T14:41:46.127Z
"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.
Huck Bennett
CC BY-SA 3.0
2015-07-16T00:55:07.320Z
2015-07-16T00:55:07.320Z
Thomas Klimpel
<p>Is the finite <a href="http://en.wikipedia.org/wiki/Inverse_semigroup">inverse semigroup</a> isomorphism problem <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem">GI-complete</a>? Here the finite inverse semigroups are assumed to be given by their multiplication tables.</p>

CC BY-SA 3.0
2015-01-08T15:13:22.413Z
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?
J.-E. Pin
CC BY-SA 3.0
2015-01-08T16:15:39.290Z
@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.
Thomas Klimpel
CC BY-SA 3.0
2015-01-09T09:35:27.023Z
Commutative class 3 nilpotent semigroups are not embeddable into inverse semigroups, according to an old result by B. Schein, cited by Mark Sapir [here](http://mathoverflow.net/a/101114). (I read a bit in the cited paper, but haven't worked through it thoroughly "yet", maybe I should.)
Thomas Klimpel
<cc.complexity-theory><graph-isomorphism>
Is the finite inverse semigroup isomorphism problem GI-complete?
Thomas Klimpel
# Is the finite inverse semigroup isomorphism problem GI-complete?

(Asked by: username_0 on 2015-01-03)

Is the finite [inverse semigroup](http://en.wikipedia.org/wiki/Inverse_semigroup) isomorphism problem [GI-complete](http://en.wikipedia.org/wiki/Graph_isomorphism_problem)? Here the finite inverse semigroups are assumed to be given by their multiplication tables.

**Tags:** cc.complexity-theory, graph-isomorphism

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_0**: Commutative class 3 nilpotent semigroups are not embeddable into inverse semigroups, according to an old result by B. Schein, cited by Mark Sapir [here](http://mathoverflow.net/a/101114). (I read a bit in the cited paper, but haven't worked through it thoroughly "yet", maybe I should.)  

---

## 1 answers

### Answer by username_0 on 2015-07-16. Score: 9 | Accepted answer

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](http://chat.stackexchange.com/transcript/message/22783789#22783789). The motivation to spend time on graph isomorphism at all also came from vzn's repeated prodding. username_1 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](https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/) and graph isomorphism, but I fear this answer doesn't provide any insight of this sort.

> **Comments:**
> **username_2**: Somewhat confusingly, there's also this lattice isomorphism problem which is GI-hard but not known to be GI-complete: http://www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf  
> **username_0**: @HuckBennett Are you really confused, or would you just like to hear my opinion on lattice theory? The name "lattice" is [simply unlucky](http://dml.cz/bitstream/handle/10338.dmlcz/401261/DejinyMat_17-2001-1_31.pdf): "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](http://dpt-info.u-strasbg.fr/~cronse/lt.html) might have been avoided by splitting it into algebraic logic, formal concept analysis, and order theory.  
> **username_2**: "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.  

---

