En la página 1 de la Conferencia 2, Álgebra y Cálculo , (Instructor del Curso: V. Arvind), hay un teorema-
Teorema 2. Con el Gráfico − Iso (gráfico isomorfismo) como un oráculo, no es un el polinomio de tiempo para el algoritmo de Gráfico − Aut (automorphism) y vice-versa.
en la página 2, la prueba está dado-
Prueba. Primero demostraremos que somos capaces de resolver el Gráfico−Iso con el Gráfico−Aut como un oráculo. Estamos dados dos grafos $G_1$ $G_2$ y necesitamos crear un grafo G el uso de los dos tal que la generación de conjunto de la automorphism nos diga si son isomorfos o no. Deje $G = G_1 \cup G_2$. Supongamos, además, sabíamos que $G_1$ y $G_2$ están conectados, entonces una sola oracle consulta sería suficiente. Si alguno de los generadores de $Aut(G)$ intercambiarse un vértice en $G_1$ con uno en $G_2$, luego connnectivity debería obligar a $G_1 \simeq G_2$. Pero, ¿y si no están conectados? Luego tenemos este muy buen truco, $G_1 \simeq G_2 \Leftrightarrow \bar G_1\simeq \bar G_2$ , y $G_1$ o $\bar G_1$ tiene que estar conectado y por lo tanto uno puede comprobar conectividad y, a continuación, pedir a la consulta adecuada.
$\bar G_1$ es el complemento gráfico de $G_1$, supongo.
Se dice que-
Supongamos, además, sabíamos que $G_1$ y $G_2$ están conectados, entonces una sola oracle consulta sería suficiente.
Pero cuando ponemos a prueba gráfica de isomorfismo, $G_1 , G_2$ son dos diferentes desconectado gráfico. Es qué no salió como-
Pero, ¿y si no están conectados? Luego tenemos este muy buen truco, $G_1 \simeq G_2 \Leftrightarrow \bar G_1\simeq \bar G_2$, y $G_1$ o $\bar G_1$ tiene que estar conectado y por lo tanto uno puede comprobar conectividad y, a continuación, pedir a la consulta adecuada.
Así, estamos comprobando si hay un automorphism de $G' = \bar G_1 \cup \bar G_2$ que swaps de un vértice de $\bar G_1$ con un vértice de $\bar G_2$?
¿Cómo podemos saber que este tipo de intercambio es un automorphism?
