¿Qué evidencia hay de que el isomorfismo gráfico no está en

Motivado por el comentario de Fortnow en mi publicación, Evidencia de que el problema del isomorfismo gráfico no es $NP$ -completo , y por el hecho de que $GI$ es un candidato principal para $NP$ -problema intermedio (no $NP$ -completo ni en $P$ ), estoy interesado en evidencias conocidos que $GI$ no está en $P$ .

Una de esas pruebas es la completitud de $NP$ de un problema restringido de Automorfismo de Gráficos (el problema de Automorfismo de gráfico libre de punto fijo es $NP$ completo). Lubiw estudió este problema y otras generalizaciones de $GI$ en " Algunos problemas NP completos similares al isomorfismo gráfico ". Algunos pueden argumentar como evidencia el hecho de que a pesar de más de 45 años, nadie encontró algoritmo de tiempo polinómico para $GI$ .

¿Qué otra evidencia tenemos para creer que $GI$ no está en $P$ ?

Antes de esta pregunta, mi opinión era que el isomorfismo gráfico podría estar en P, es decir, que no hay evidencia para creer que GI no está en P. Por lo tanto, me pregunté qué sería una evidencia para mí: si hubiera algoritmos maduros para - el isomorfismo grupal que explotó completamente la estructura disponible de los grupos p y aún no tenía esperanza de lograr un tiempo de ejecución polinomial, entonces estaría de acuerdo en que GI probablemente no está en P. Hay algoritmos conocidos que explotan la estructura disponible como las pruebas de isomorfismo para p - grupos por O'Brien (1994)$p$$p$$p$, pero no lo he leído con suficiente detalle para juzgar si explota completamente la estructura disponible, o si hay alguna esperanza de mejorar este algoritmo (sin explotar la estructura adicional no obvia de los grupos ) para lograr el tiempo de ejecución polinomial.$p$

Pero sabía que Dick Lipton llamó a la acción a fines de 2011 para aclarar la complejidad computacional del problema del isomorfismo grupal en general, y del problema del isomorfismo del grupo específicamente. Así que busqué en Google$p$

site:https://rjlipton.wordpress.com group isomorphism

para ver si el llamado a la acción había sido exitoso. Era de hecho:

1. El problema del isomorfismo grupal: ¿un posible problema polimático?
2. Avances en el isomorfismo grupal
3. Tres de CCC: progreso en el isomorfismo grupal

La última publicación revisa un artículo que logra el tiempo de ejecución para ciertas familias importantes de grupos, explota gran parte de la estructura disponible y reconoce el documento mencionado anteriormente de 1994. Porque el tiempo de ejecución n O ( log log n ) está vinculado es compatible con la experiencia de que el isomorfismo gráfico no es difícil en la práctica, y con la experiencia de que nadie puede llegar a un algoritmo de tiempo polinómico (incluso para el isomorfismo grupal), esto se puede contar como evidencia de que GI no está en P .$n^{O(\log \log n)}$$n^{O(\log \log n)}$

¡El conjunto más pequeño de permutaciones que debe verificar para verificar que no existan permutaciones no triviales en un cuadro negro es mejor que pero aún exponencial, OEIS A186202 .$n!$

El número de bits necesarios para almacenar un gráfico sin etiquetar es de ($log_{2}$. Ver Naor, Moni. "Representación sucinta de gráficos generales sin etiquetar". Matemática Aplicada Discreta 28.3 (1990): 303-307. La prueba del método de compresión es un poco más limpia si no recuerdo mal. De todos modos, vamos llamada que estableceT. DejeL=2 (${n\choose 2}-n log(n) +O(n)$$U$ para gráficos etiquetados.$L=2^{{n\choose 2}}$

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

y B o o l L L si convierte a exponenciales. Simplemente examinar sus firmas tipo poner gráficos en forma canónica parece más fácil, pero como se muestra arriba, GC facilita la IG.$U^L$$Bool^{L^{L}}$

Kozen en su papel, Un problema camarilla equivalente a isomorfismo gráfico , da una evidencia de que no está en P . Lo siguiente es del documento:$GI$$P$

"Sin embargo, es probable que encontrar un algoritmo de tiempo polinómico para el isomorfismo gráfico sea tan difícil como encontrar un algoritmo de tiempo polinómico para un problema de NP completo. En apoyo de esta afirmación, damos un problema equivalente al isomorfismo gráfico, una pequeña perturbación de los cuales es NP-completo ".

Además, Babai, en su reciente y novedoso trabajo Graph Isomorphism in cuasipolynomial time, presenta un argumento en contra de la existencia de algoritmos eficientes para GI. Se observa que el problema grupo isomorfismo (que es reducible a GI) es un obstáculo importante para la colocación de GI en . Problema Grupo isomorfismo (grupos están dadas por su Tableis Cayley) es resoluble en n O ( log n ) y no se sabe que estar en P .$P$$n^{O(\log n)}$$P$

Aquí hay un extracto del artículo de Babai:

El resultado del presente trabajo amplifica la importancia del problema del isomorfismo grupal (y el problema de desafío declarado) como una barrera para colocar GI en P. Es muy posible que el estado intermedio de GI (ni NP-completo, ni tiempo polinomial) persistirá

Aquí hay otros resultados aún no citados

• Sobre la dureza del isomorfismo gráfico / Torán FOCS 2000 y SIAM J. Comput. 33, 5 1093-1108.

  Mostramos que el problema del isomorfismo gráfico es difícil bajo DLOGTIME reducciones de AC ⁰ muchos-uno para las clases de complejidad NL, PL (espacio logarítmico probabilístico) para cada clase de espacio modular logarítmico Mod _k L y para la clase DET de problemas NC ¹ reducible a El determinante. Estos son los resultados de dureza más fuertes conocidos para el problema del isomorfismo gráfico e implican una reducción aleatoria del espacio logarítmico del problema de coincidencia perfecta al isomorfismo gráfico. También investigamos los resultados de dureza para el problema del automorfismo gráfico.

• El isomorfismo gráfico no es AC ⁰ reducible a isomorfismo grupal / Chattopadhyay, Toran, Wagner

  Damos un nuevo límite superior para los problemas de isomorfismo de grupo y cuasigrupo cuando las estructuras de entrada se dan explícitamente en tablas de multiplicar. Mostramos que estos problemas pueden calcularse mediante circuitos no deterministas de tamaño polinómico de abanico ilimitado con profundidad O (log log n) y O (log ² n) bits no deterministas, donde n es el número de elementos del grupo. Esto mejora el límite superior existente de [Wol94] para los problemas. En el límite superior anterior, los circuitos tienen límites de fanin pero profundidad O (log ² n) y también O (log ² n) bits no deterministas. Luego demostramos que el tipo de circuitos de nuestro límite superior no puede calcular la función de paridad. Como la paridad es AC ⁰reducible al isomorfismo gráfico, esto implica que el isomorfismo gráfico es estrictamente más difícil que el isomorfismo de grupo o cuasigrupo bajo el orden definido por las reducciones de AC ⁰ .