¿El problema de isomorfismo de semigrupo inverso finito es GI completo?

11

¿El problema de isomorfismo de semigrupo inverso finito es GI completo ? Aquí se supone que los semigrupos inversos finitos están dados por sus tablas de multiplicar.

cc.complexity-theory graph-isomorphism Thomas Klimpel
fuente
¿Hay alguna razón específica para considerar los semigrupos inversos? ¿Qué se sabe sobre la complejidad del problema de isomorfismo de grupo finito y el problema de isomorfismo de semigrupo finito?
J.-E.
1
@ J.-E.Pin El problema de isomorfismo de semigrupo finito es GI completo, no se sabe que el problema de isomorfismo de grupo finito sea GI completo. El artículo de wikipedia vinculado en la pregunta establece que el isomorfismo de "clase conmutativa nilpotente clase 3 (es decir, para cada semigrupos de elementos x , y , z )" es GI completo. xyz=0x,y,z
Thomas Klimpel
1
Los semigrupos conmutativos nilpotentes de clase 3 no pueden integrarse en semigrupos inversos, según un viejo resultado de B. Schein, citado aquí por Mark Sapir . (Leí un poco en el documento citado, pero no lo he revisado a fondo "todavía", tal vez debería.)
Thomas Klimpel

Respuestas:

9

Sí, ¡el problema de isomorfismo de semigrupo inverso finito es GI completo! Este es un corolario de

Teorema: el isomorfismo del enrejado es isomorfismo completo

de la sección 7.2 Enrejados y Posets en

Booth, Kellogg S .; Colbourn, CJ (1977), Problemas polinomialmente equivalentes al isomorfismo gráfico, Informe técnico CS-77-04, Departamento de Informática, Universidad de Waterloo.

porque una (semi-) red también es un semigrupo inverso (idempotente conmutativo).

Prueba de teorema del informe técnico:

Gnm'0''1''1''0'G

La idea de esta respuesta surgió de una discusión con vzn sobre preguntas suficientemente enfocadas . La motivación para dedicar tiempo al isomorfismo gráfico también provino de la repetida insistencia de vzn. J.-E. Pin preguntó en el comentario si hay alguna razón específica para considerar los semigrupos inversos. La idea era tener una estructura de grupos ligeramente generalizadores, que es GI completo. Quería comprender mejor la relación entre el isomorfismo grupal y el isomorfismo gráfico, pero me temo que esta respuesta no proporciona ninguna idea de este tipo.

Thomas Klimpel
fuente
2
Algo confuso, también existe este problema de isomorfismo reticular que es GI duro pero no se sabe que es GI completo: www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf
Huck Bennett
1
@HuckBennett ¿Estás realmente confundido o te gustaría escuchar mi opinión sobre la teoría de la red? El nombre "celosía" es simplemente desafortunado : "G. Birkhoff también introdujo la palabra inglesa" celosía ", que no es la traducción de su equivalente alemán, sino que se inspiró en la imagen de algunos diagramas de Hasse que presentan celosías". La mala reputación de la teoría de la red podría haberse evitado dividiéndola en lógica algebraica, análisis de concepto formal y teoría del orden.
Thomas Klimpel
1
"¿Estás realmente confundido o te gustaría escuchar mi opinión sobre la teoría de la red?" Ninguno de los dos, en realidad. Pensé que alguien además de mí podría haber estado familiarizado con esa definición de isomorfismo reticular y no con esta, y que el enlace podría ayudar.
Huck Bennett