Grupo de isomorfismo para graficar ismorfismo

Al leer algunos blogs sobre la complejidad computacional (por ejemplo, aquí ) asimilé la noción de que decidir si dos grupos son isomórficos es más fácil que probar dos gráficos para el isomorfismo. Por ejemplo, en la página indicada dice que el isomorfismo gráfico es un problema más general que el isomorfismo grupal.

Por lo tanto, estoy planteando lo siguiente

Dado un grupo ¿alguien puede dar una construcción de un gráfico de polinomio de tamaño ental que para los grupos y$G$$\Gamma(G)$$|G|$

$$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ $G$$H?$

La reducción se describe en un artículo clásico de Miller.

No tan rapido. Aquí hay una gran ambigüedad al acecho:

¿Cómo ingresas tu grupo para el cálculo?

A diferencia de los gráficos, los grupos se pueden ingresar por medios que son muy diferentes en términos de tamaño de entrada y complejidad resultante. La versión citada en Miller es una de las menos naturales y, por ejemplo, no la encontrarás en un sistema de álgebra computacional como GAP, Magma o Sage. Entonces, si bien tiene una premisa teórica, iría demasiado lejos para llamar a eso resolver el problema.

1. Generadores y relaciones: el isomorfismo grupal es indecidible (el isomorfismo gráfico es decidible).

Si la historia es la ganadora, la primera mención del problema del isomorfismo grupal fue por Max Dehn en 1905. Asumió que los grupos serían aportados por generadores y relaciones. Adyan y Rabin en la década de 1950 demostraron que el problema es indecidible . Esta situación ocurre incluso si el grupo es trivial. Entonces no es solo un problema de cardinalidad. El problema clave es que puede crear grupos donde decidir si sería resolver un problema de reescritura que no sea primitivo recursivo. Similar a los problemas de tipo de detención, no se puede hacer.$G$$G=1$

Para grupos aportados por generadores y relaciones: el isomorfismo grupal es más difícil que el isomorfismo gráfico, de hecho es indecidible.

2. Entradas utilizadas por los sistemas de software: el isomorfismo grupal de permutación y los grupos matriciales son al menos tan duros como el isomorfismo gráfico (no al revés).

Este modelo de entrada supone que los grupos están codificados de alguna manera natural, por ejemplo, como permutaciones en un conjunto finito, o como matrices sobre un anillo o campo. Estos son los métodos introducidos por Cannon y Neubuser en los primeros sistemas de álgebra computacional en la década de 1960 que pasaron a ser GAP y Magma. En este modelo, puede incrustar el problema de isomorfismo gráfico en el problema de isomorfismo grupal. Ver, por ejemplo, el trabajo de Heinekin-Liebeck. Desde entonces ha sido llevado a cabo en otras formas por otros como Sergeichuk. La idea clave es integrar la matriz de adyacencia de un gráfico en las relaciones de un grupo .$p$

Para entrada de grupos para sistemas de software: el isomorfismo grupal es al menos tan difícil como el isomorfismo gráfico.

3. Entradas de Complejidad teórica: para una entrada de grupo de recuadro negro, no se sabe que el isomorfismo de grupo esté en NP o co-NP (el isomorfismo de gráfico está en ambos).

Este es un modelo para grupos sugerido por Babai-Szemeredi que no asume nada acerca de la entrada, excepto que debe contar con funciones (costo unitario) para que las operaciones de grupo se multipliquen, inviertan, prueben la igualdad y un conjunto de generadores. En su artículo "Sobre la complejidad de los problemas de los grupos de matrices", discuten este problema y concluyen que está en . El problema clave es que ni siquiera puede definir un certificado de isomorfismo (por lo tanto, no está en NP) porque solo tiene generadores de los grupos. Entonces, para proporcionar un isomorfismo real no es posible, y son exponencialmente más grandes y solo de los generadores no se puede saber si$\Sigma^2$$f:G\to H$$G$$H$$f$Es un homomorfismo válido. Como mínimo, parece necesitar una presentación de los grupos, y eso no se obtiene fácilmente.

Para grupos de caja negra: el isomorfismo grupal es al menos tan duro como el isomorfismo gráfico.

4. Entradas de tabla Cayley.

En algún momento de la década de 1970, Tarjan, Pultr-Hederlon, Miller y otros observaron que los aportes de los grupos por toda su tabla de multiplicación también podrían tratarse como gráficos. De esta manera, el isomorfismo grupal se reduce al isomorfismo gráfico en el tiempo polinomial. Miller fue mucho más lejos al observar que numerosas estructuras combinatorias hacen lo mismo, Steiner se triplica, por ejemplo. También demostró que el isomorfismo del semigrupo es equivalente al isomorfismo gráfico.

Recientemente, Babai demostró que el isomorfismo gráfico está en tiempo cuasi polinomial y las reducciones ahora estiman una complejidad de aproximadamente , que es precisamente el límite más conocido para el isomorfismo grupal para grupos dados por la tabla de Cayley. Si bien nadie ha demostrado que estos dos problemas sean equivalentes al tiempo polinómico, los tiempos de presentación sugieren una relación más cercana de lo esperado.$n^{O(\log n)}$

Para las tablas de Cayley: el isomorfismo grupal se reduce a isomorfismo gráfico.

¿Qué entrada es la entrada de grupo "correcta"? Bueno, la complejidad de Kolmogorov del grupo finito de orden es que es aproximadamente el tamaño de entrada de los métodos 1-3 anteriores. Esos métodos de entrada son naturales y fáciles de crear, por ejemplo, calculando la generación de permutaciones de un cubo de Rubik o observando la generación de bucles de un grupo fundamental. Por lo tanto, tiene sentido que gran parte de la teoría y la práctica del isomorfismo grupal utilicen esos modelos.$n$$O((\log n)^3)$

Sin embargo, aunque ningún sistema de álgebra computacional usa tablas de Cayley, y la mayoría de las ciencias de la computación teóricas usan estructuras como grupos de permutación, grupos de matriz y grupos de caja negra, todavía hay una buena defensa para la perspectiva de la tabla de Cayley. En general, la complejidad de estructuras de Kolmogorov, como los semigrupos, es de orden es , un teorema de Marshall Hall. Por lo tanto, no podría ingresar semigrupos de manera más concisa que mediante la tabla de multiplicar. Por lo tanto, cuando desee comparar la complejidad del isomorfismo grupal con otras estructuras naturales (cuasi grupos, bucles, semigrupos, etc.) tiene sentido acordar un modelo de entrada común.$n$$O(n^2 \log n)$