Graficar isomorfismo y subgrupos ocultos

Estoy tratando de entender la relación entre el isomorfismo gráfico y el problema oculto de subgrupos. ¿Hay una buena referencia para esto?

Se pueden encontrar referencias en la respuesta de martinschwarz, pero aquí hay un resumen de un par de reducciones.

El grupo simétrico actúa sobre gráficas de n vértices al permutar los vértices. Determinar si dos gráficos son isomórficos es un tiempo de polinomio equivalente a calcular un conjunto generador de tamaño polinómico para A u t ( G ) .$S_n$$Aut(G)$

Reducción al HSP sobre el grupo simétrico (donde n es el número de variables en el gráfico). La función f es f ( p ) = p ( G ) , donde p es una permutación en S n , y p ( G ) es la versión permutados de G . Entonces f es constante en cosets de A u t ( G ) y distinto en cosets distintos (tenga en cuenta que la imagen de $S_n$$n$$f$$f(p)=p(G)$$p$$S_n$$p(G)$$G$$f$$Aut(G)$$f$consiste en todos los gráficos isomorfos a ). Dado que el subgrupo oculto es exactamente A u t ( G ) , si pudiéramos resolver este HSP, tendríamos el conjunto generador para A u t ( G ) , que es todo lo que necesitamos para resolver GI (ver arriba).$G$$Aut(G)$$Aut(G)$

Reducción al HSP más de . Si queremos saber si dos gráficos G y H en n vértices son isomórficos, considere el gráfico K, que es la unión disjunta de G y H en 2 n vértices. Deje Z / 2 Z actúan sobre los vértices mediante el canje de i con n + i para i = 1 , . . . , N . Ya sea $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$ o A u t ( K ) = ( A u t ( G ) × A u t ( H ) ) s e m i d i r e c t Z / 2 Z . Como antes, deje f ( $Aut(K) = Aut(G) \times Aut(H)$$Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ donde x es ahora un elemento de S n ≀ Z / 2 Z que actúa sobre K como se describe. El subgrupo oculto asociado a f es exactamente A u t ( K ) , como en la reducción anterior. Si resolvemos este HSP, obtenemos un conjunto generador para A u t ( K ) . Entonces es fácil verificar si el conjunto generador contiene algún elemento que intercambie la copia de G con la copia de H dentro$f(x)=x(K)$$x$$S_n \wr \mathbb{Z}/2\mathbb{Z}$$K$$f$$Aut(K)$$Aut(K)$$G$$H$ (tienecomponente Z / 2 Z no trivial).$K$$\mathbb{Z}/2\mathbb{Z}$

Es posible que desee leer la reciente publicación de blog de Dave Bacon sobre isomorfismo gráfico con enlaces a la literatura.

"Algoritmos cuánticos para problemas algebraicos" por Andrew Childs y Wim van Dam arXiv: 0812.0380 es un muy buen trabajo de encuesta que contiene una buena introducción del HSP no abeliano y su relación con el isomorfismo gráfico.