Isomorfismo de gráfico e subgrupos ocultos

Estou tentando entender a relação entre isomorfismo de gráfico e o problema de subgrupo oculto. Existe uma boa referência para isso?

As referências podem ser encontradas na resposta de martinschwarz, mas aqui está um resumo de algumas reduções.

O grupo simétrico atua nos gráficos de n vértices permutando os vértices. Determinar se os dois gráficos são isomorfos é de tempo polinomial equivalente para computar um conjunto gerador de tamanho polinomial para um u t ( L ) .$S_n$$Aut(G)$

Redução para o HSP sobre o grupo simétrico (onde n é o número de variáveis ​​no gráfico). A função F é f ( P ) = P ( L ) , onde P é uma permutação em S n , e p ( L ) é a versão permutada de L . Em seguida, f é constante em classes laterais de uma u t ( G ) e distinto em classes laterais distintas (nota que a imagem de $S_n$$n$$f$$f(p)=p(G)$$p$$S_n$$p(G)$$G$$f$$Aut(G)$$f$consiste em todos os gráficos isomórficos para ). Desde o subgrupo escondido é exatamente A u t ( G ) , se pudéssemos resolver este HSP então teríamos o grupo gerador para A u t ( G ) , que é tudo o que precisamos para resolver GI (veja acima).$G$$Aut(G)$$Aut(G)$

A redução para a HSP mais de . Se queremos saber se dois gráficos G e H nos n vértices são isomórficos, considere o gráfico K, que é a união disjunta de G e H nos 2 n vértices. Deixe- Z / 2 Z agir sobre os vértices trocando i com n + i para i = 1 , . . . , N . Qualquer $S_n \wr \mathbb{Z}/2\mathbb{Z}$$G$$H$$n$$K$$G$$H$$2n$$\mathbb{Z}/2\mathbb{Z}$$i$$n+i$$i=1,...,n$ ou um u t ( K ) = ( A u t ( L ) x Um u t ( H ) ) s e m i d i r e c t Z / 2 Z . Como antes, deixe f ( $Aut(K) = Aut(G) \times Aut(H)$$Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ onde x é agora um elemento de S n ≀ Z / 2 Z que age em K como descrito. O subgrupo escondido associada a f é exactamente Um u t ( K ) , como na redução anterior. Se resolvermos este HSP, temos um grupo gerador para A u t ( K ) . É fácil verificar se o grupo gerador contém algum elemento que troque a cópia de G pela cópia de H dentro$f(x)=x(K)$$x$$S_n \wr \mathbb{Z}/2\mathbb{Z}$$K$$f$$Aut(K)$$Aut(K)$$G$$H$ (possuicomponente Z / 2 Z não trivial).$K$$\mathbb{Z}/2\mathbb{Z}$

Você pode ler a recente postagem no blog de Dave Bacon sobre Graph Isomorphism, com links para a literatura.

"Algoritmos quânticos para problemas algébricos" de Andrew Childs e Wim van Dam arXiv: 0812.0380 é um artigo de pesquisa muito bom que contém uma boa introdução ao HSP não-abeliano e sua relação com o isomorfismo de grafos.