Graficar isomorfismo y subgrupos ocultos

23

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

cc.complexity-theory reference-request quantum-computing graph-isomorphism Suresh Venkat
fuente

2

¡Tssk, no solo necesitaremos curar su enfermedad gastrointestinal, sino también a todos los lectores pobres de su pregunta que también se infectan! (Esto es una broma, también soy algo propenso a la enfermedad gastrointestinal.)

András Salamon

1

demasiado cierto. Tengo que alejarme de Dave Bacon ahora :)

Suresh Venkat

2

Para su información, creo que el siguiente artículo relativamente reciente puso el clavo en el ataúd sobre "algoritmos de tamiz cuántico" para GI, que cubre muchos de los intentos hasta ahora (y no se menciona en la publicación del blog de Dave Bacon): dx.doi.org/ 10.1137 / 080724101 . El documento es pesado en la teoría de la representación, pero la introducción no lo es, y es una lectura bastante buena.

Joshua Grochow

20

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 . $S_n$ $Aut(G)$

Reducción al HSP sobre el grupo simétrico (donde es el número de variables en el gráfico). La función es , donde es una permutación en , y es la versión permutados de . Entonces es constante en cosets de 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 , si pudiéramos resolver este HSP, tendríamos el conjunto generador para , 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 y en vértices son isomórficos, considere el gráfico que es la unión disjunta de y en vértices. Deje actúan sobre los vértices mediante el canje de con para . 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 . Como antes, deje $Aut(K) = Aut(G) \times Aut(H)$ $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ donde es ahora un elemento de que actúa sobre como se describe. El subgrupo oculto asociado a es exactamente , como en la reducción anterior. Si resolvemos este HSP, obtenemos un conjunto generador para . Entonces es fácil verificar si el conjunto generador contiene algún elemento que intercambie la copia de con la copia de dentro $f(x)=x(K)$ $x$ $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $K$ $f$ $Aut(K)$ $Aut(K)$ $G$ $H$ (tienecomponente no trivial). $K$ $\mathbb{Z}/2\mathbb{Z}$

Joshua Grochow
fuente

17

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

Martin Schwarz
fuente

14

"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.

dabacon
fuente

Graficar isomorfismo y subgrupos ocultos

Respuestas: