Agrupe isomorfismo para representar graficamente ismorfismo

12

Ao ler alguns blogs sobre complexidade computacional (por exemplo, aqui ), eu assimilei a noção de que decidir se dois grupos são isomórficos é mais fácil do que testar dois gráficos quanto ao isomorfismo. Por exemplo, na página declarada, diz que o isomorfismo do gráfico é um problema mais geral que o isomorfismo do grupo.

Portanto, eu estou colocando o seguinte

Dado um grupo alguém pode dar uma construção de um gráfico de tamanho polinomial emtal que para os grupos eGΓ(G)|G|

Γ(G)Γ(H)GH
GH?
Jernej
fonte
enquanto os dois estão fortemente acoplados como observado e pesquisada há décadas, AFAICT isomorfismo grupo não é realmente provou "mais fácil" do que o gráfico isomorfismo ou seja, sua aproximadamente uma importante questão em aberto como a sua complexidade é exatamente relacionado. também seria útil se você explicitasse também a relação matemática em palavras.
vzn

Respostas:

12

A redução é descrita em um artigo clássico de Miller.

Yuval Filmus
fonte
4

Não tão rápido. Há uma grande ambiguidade à espreita aqui:

Como você insere seu grupo para computação?

Ao contrário dos gráficos, os grupos podem ser inseridos por meios muito diferentes em termos de tamanho de entrada e complexidade resultante. A versão citada em Miller é uma das menos naturais e, por exemplo, você não encontrará isso em um sistema de álgebra computacional como GAP, Magma ou Sage. Portanto, embora tenha uma premissa teórica, seria muito longe chamar isso de resolver o problema.


  1. Geradores e relações: O isomorfismo do grupo é indecidível (o isomorfismo do gráfico é decidível).

Se a história é a vencedora, a primeira menção ao problema do isomorfismo de grupo foi por Max Dehn em 1905. Ele assumiu que os grupos seriam inseridos por geradores e relações. Adyan e Rabin nos anos 50 provaram que o problema é indecidível . Essa situação ocorre mesmo se o grupo for trivial. Portanto, não é apenas uma questão de cardinalidade. O principal problema é que você pode criar grupos onde decidir se seria resolver um problema de reescrita que é recursivo não primitivo. Semelhante aos problemas do tipo Halting, não pode ser feito.GG=1

Para grupos introduzidos por geradores e relações: o isomorfismo de grupo é mais difícil que o isomorfismo de gráfico, de fato indecidível.

  1. Entradas usadas pelos sistemas de software: o isomorfismo de grupo de permutação e os grupos de matrizes são pelo menos tão difíceis quanto o isomorfismo de gráfico (não o contrário).

Esse modelo de entrada assume que os grupos são codificados de alguma maneira natural, digamos como permutações em um conjunto finito ou como matrizes em um anel ou campo. Estes são os métodos introduzidos por Cannon e Neubuser nos primeiros sistemas de álgebra computacional na década de 1960, que passaram a ser GAP e Magma. Neste modelo, você pode incorporar o problema de isomorfismo gráfico no problema de isomorfismo de grupo. Veja, por exemplo, o trabalho de Heinekin-Liebeck. Desde então, foi realizado de outras formas por outros, como Sergeichuk. A idéia principal é incorporar a matriz de adjacência de um gráfico nas relações de um grupo- .p

Para entrada de grupos em sistemas de software: o isomorfismo de grupo é pelo menos tão difícil quanto o isomorfismo de gráfico.

  1. Entradas de complexidade teórica: para uma entrada de grupo de caixa preta, o isomorfismo do grupo não é conhecido como NP ou co-NP (o isomorfismo gráfico está em ambos).

Σ2f:GHGHfé um homomorfismo válido. No mínimo, você parece precisar de uma apresentação dos grupos, e isso não é facilmente obtido.

Para grupos de caixas pretas: o isomorfismo de grupo é pelo menos tão difícil quanto o isomorfismo de gráfico.

  1. Entradas da tabela de Cayley.

Em algum momento da década de 1970, Tarjan, Pultr-Hederlon, Miller e outros observaram que os grupos inseridos em toda a sua tabuada de multiplicação também podiam ser tratados como gráficos. Dessa maneira, o isomorfismo de grupo reduz ao gráfico o isomorfismo em tempo polinomial. Miller foi muito além ao observar que numerosas estruturas combinatórias fazem o mesmo, Steiner triplica, por exemplo. Ele também demonstrou que o isomorfismo do semigrupo é equivalente ao isomorfismo do gráfico.

nO(registron)

Para tabelas Cayley: o isomorfismo de grupo se reduz ao isomorfismo de gráfico.


nO((registron)3)

nO(n2registron)

Algeboy
fonte
Obrigado por toda a discussão útil. Um ponto: onde você escreve "Para entrada de grupos em sistemas de software: o isomorfismo de grupo é mais difícil que o isomorfismo de gráfico", você tem uma citação para a alegação de que é mais difícil (e não pelo menos tão difícil )? "Mais difícil" tenderia a sugerir que as complexidades não são iguais. Existe alguma evidência disso? Ou você realmente quis dizer "pelo menos tão difícil"?
DW
Opa, que vergonha para mim ", pelo menos tão difícil quanto" seria o que se sabe. Desigualdade estrita de complexidade é como você diz - rara. No entanto, pode-se observar que problemas como a equivalência de código (relacionada ao isomorfismo do hipergrafo) geralmente é o problema que se pode reduzir do isomorfismo de grupo nesses modelos. A equivalência de código continua a ser uma complexidade exponencial, mesmo após a quebra de Babai pelo isomorfismo gráfico em tempo quase polinomial. Portanto, isso fornece evidências fracas para "mais difícil", mas nenhuma prova de estritamente mais difícil é conhecida. Eu vou corrigir o acima. Obrigado.
Algeboy 22/09