O problema do isomorfismo inverso semigrupo finito é GI-completo?

11

O problema do isomorfismo inverso semigrupo finito é GI-completo ? Aqui, supõe-se que os semigrupos inversos finitos sejam dados por suas tabelas de multiplicação.

cc.complexity-theory graph-isomorphism Thomas Klimpel
fonte
Existe algum motivo específico para considerar semigrupos inversos? O que se sabe sobre a complexidade do problema de isomorfismo de grupos finitos e do isomorfismo de semigrupos finitos?
J.-E.
1
@ J.-E.Pin O problema do isomorfismo do semigrupo finito é GI completo, o problema do isomorfismo do grupo finito não é conhecido por ser GI completo. O artigo da wikipedia vinculado na pergunta afirma que o isomorfismo de "semutupos comutativos de classe 3 nilpotentes (ou seja, para todos os semigrupos de todos os elementos x , y , z )" está completo em GI. xyz=0x,y,z
Thomas Klimpel
1
Os semigrupos comutativos de classe 3 sem potências não são incorporáveis ​​em semigrupos inversos, de acordo com um antigo resultado de B. Schein, citado por Mark Sapir aqui . (Eu li um pouco no documento citado, mas não tenho trabalhado com ele completamente "ainda", talvez eu deveria.)
Thomas Klimpel

Respostas:

9

Sim, o problema de isomorfismo do semigrupo inverso finito é GI-completo! Este é um corolário de

Teorema: Isomorfismo da rede isomorfismo completo

da seção 7.2 Malhas e Posets em

Booth, Kellogg S .; Colbourn, CJ (1977), Problemas polinomialmente equivalentes ao isomorfismo de grafos, Relatório Técnico CS-77-04, Departamento de Ciência da Computação, Universidade de Waterloo.

porque uma (semi-) rede é também um semigrupo inverso (comutativo idempotente).

Prova de teorema do relatório técnico:

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

A idéia para esta resposta veio de uma discussão com vzn sobre perguntas suficientemente focadas . A motivação para dedicar algum tempo ao isomorfismo gráfico também veio do estímulo repetido de vzn. J.-E. Pin perguntou no comentário se existem razões específicas para considerar semigrupos inversos. A idéia era ter uma estrutura que generalizasse os grupos, que é GI completa. Eu queria entender melhor a relação entre isomorfismo de grupo e isomorfismo de gráfico, mas temo que essa resposta não forneça qualquer insight desse tipo.

Thomas Klimpel
fonte
2
Um pouco confusa, há também este problema isomorfismo treliça que é GI-duro, mas não conhecido por ser GI-completa: www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf
Huck Bennett
1
@HuckBennett Você está realmente confuso ou gostaria de ouvir minha opinião sobre a teoria das redes? O nome "treliça" é simplesmente azarado : "G. Birkhoff também introduziu a palavra em inglês" treliça ", que não é a tradução de seu equivalente alemão, mas foi inspirada pela imagem de alguns diagramas de Hasse apresentando treliça". A má reputação da teoria da rede pode ter sido evitada dividindo-a em lógica algébrica, análise formal de conceito e teoria da ordem.
22415 Thomas Thomas Klimpel
1
"Você está realmente confuso, ou gostaria de ouvir minha opinião sobre a teoria das redes?" Nem, na verdade. Eu pensei que alguém além de mim pudesse estar familiarizado com essa definição de isomorfismo da rede e não com essa, e que o link poderia ajudar.
Huck Bennett