Consecuencias de un algoritmo de tiempo cuasi-polinomial para el problema de isomorfismo gráfico

El problema del isomorfismo gráfico (IG) es posiblemente el candidato más conocido para un problema NP-intermedio . El algoritmo más conocido es el algoritmo sub-exponencial con tiempo de ejecución . Se sabe que GI no esNP-completo a menos que lajerarquía polinómica secolapse.$2^{O(\sqrt{n \log n})}$$\mathsf{NP}$

¿Cuáles serían las consecuencias teóricas de la complejidad de un algoritmo de tiempo cuasi-polinomial para el problema del isomorfismo gráfico?
¿Un algoritmo de tiempo cuasi-polinomial para IG refutaría cualquier conjetura famosa en la teoría de la complejidad?

Otros problemas similares, como el problema de Dominio mínimo establecido en torneos, el problema de isomorfismo de grupo y el problema de isomorfismo de torneo tienen algoritmos de tiempo cuasi polinomial ( QP ). Los dos problemas posteriores son el tiempo polinómico reducible a GI.

¿Podemos reducir eficientemente el problema de Dominio mínimo establecido en torneos a IG?
¿Hay alguna conjetura que descarte que GI sea difícil para QP?

Actualización (2015-12-14) : Babai ha publicado un borrador preliminar en arXiv para su algoritmo de tiempo cuasipolinomial para IG.

Actualización (2017-01-04) : Babai retractó de la afirmación de que el algoritmo está en tiempo cuasipolinomial, según el nuevo análisis, el algoritmo está en tiempo subexponencial que está dentro de .2 n o ( 1 $\exp \exp(\tilde{O}(\sqrt{\lg n}))$$2^{n^{o(1)}}$

Actualización (2017-01-09) : Babai restableció el reclamo de tiempo cuasipolinomial, reemplazando el procedimiento infractor por uno más eficiente.

Por lo que puedo decir, si preguntas simplemente sobre las consecuencias del mero hecho (como una caja negra) de que GI está en QP, creo que la respuesta es muy pequeña. Lo único que se me ocurre, que no es un teorema sino una consecuencia de las instrucciones de investigación, es Agrupar isomorfismo . Dado que GroupIso se reduce a GI y ni siquiera sabemos si GroupIso está en P, poner GroupIso en P puede verse como un obstáculo importante para poner GI en P (si cree que este podría ser el caso).

Sin embargo, dado que el algoritmo trivial para GroupIso es , cuando la complejidad de GI estaba en 2 ˜ O$n^{\log n + O(1)}$, teníamos un largo camino por recorrer para mejorar la complejidad de GI antes de que GroupIso se convirtiera en unobstáculoinmediatamente relevantepara poner GI en P. Pero si GI está en QP, entonces GroupIso se convierte en un obstáculo mucho más relevante para futuras mejoras en GI. (Por supuesto, el exponente del exponente en el cuasi-polinomio sigue siendo una brecha potencialmente relevante, pero la brecha se vuelvemuchomás pequeña cuando GI está en QP).$2^{\tilde O(\sqrt{n})}$

$\varnothing$$\Sigma^*$

¿Cuáles serían las consecuencias teóricas de la complejidad de un algoritmo de tiempo cuasi-polinomial para el problema del isomorfismo gráfico?

Más o menos similar a las consecuencias del algoritmo de tiempo polinomial determinista para la prueba de primalidad, el algoritmo de tiempo polinomial determinista para programación lineal y el otro caso donde se conocían algoritmos prácticamente eficientes (aleatorizados) (con ejemplos patológicos raros donde el algoritmo se volvió ineficiente) y en uso durante mucho tiempo. Confirma la conjetura de que la eficiencia práctica es un buen indicador de la existencia de algoritmos teóricos deterministas que superan los problemas de los raros ejemplos patológicos.

¿Un algoritmo de tiempo cuasi-polinomial para IG refutaría cualquier conjetura famosa en la teoría de la complejidad?

No, las conjeturas más bien van al sitio opuesto, es decir, que GI está en P. Dado que GI está en NP, no será posible refutar este tipo de conjeturas en el corto plazo.

¿Podemos reducir eficientemente el problema de Dominio mínimo establecido en torneos a IG?

El conjunto de dominación mínima no es un problema de isomorfismo, por lo tanto, no hay ninguna razón por la que deba esperarse que sea reducible a IG.

¿Hay alguna conjetura que descarte que GI sea difícil para QP?

Ni siquiera sabemos cómo reducir el problema del isomorfismo de cuerdas a IG, y esto es al menos un problema de isomorfismo. La prueba de Babai mostró que el isomorfismo de cuerdas estaba en QP, así que ... ¿Y qué se supone que significa ser difícil para QP? ¿Duro bajo reducciones de tiempo polinomiales?

De la introducción de Sobre el grupo y los problemas de isomorfismo de color por François Le Gall y David J. Rosenbaum

La complejidad de los problemas de prueba de isomorfismo es digna de estudio, ya que son preguntas computacionales fundamentales y también porque no se sabe que muchos de ellos están en P, pero sin embargo parecen ser más fáciles que los problemas NP-completos. El más estudiado de estos es el problema del isomorfismo gráfico.

$\mathsf{GI}^*$$\mathsf{GrI}^*$se definen (en el documento anterior, pero los autores se preguntan con razón por qué nadie lo hizo antes), que agregan las piezas que faltan del problema del isomorfismo de cuerdas. (Y el problema de isomorfismo de color es solo un nombre diferente para el problema de isomorfismo de cadena. El problema de automorfismo de color de nombre se remonta a los documentos iniciales de Babai y Luks, el nombre de isomorfismo de cadena aparece más adelante en su documento sobre etiquetado canónico).

$\mathsf{GI}^*$

Editar: Esta respuesta se dio en el contexto de la retracción del resultado de Babai, antes de que anunciara una solución. Sugiere que la ligera generalización del problema de isomorfismo gráfico sugerida por el problema de isomorfismo de cuerdas es el problema realmente importante. La expectativa implícita aquí es que cualquier algoritmo razonable para el problema del isomorfismo del gráfico conducirá a un algoritmo similar para el problema del isomorfismo del gráfico generalizado. El problema generalizado es el tiempo polinómico equivalente al problema del estabilizador de conjunto , el problema de intersección de grupo , el problema de intersección de coset, el problema de transportador de conjunto , ... La idea detrás de esta expectativa es que el problema generalizado ocurrirá en la parte recursivade cualquier algoritmo razonable, por lo que debe abordarse de todos modos. (Y es muy posible que el problema generalizado sea el tiempo polinómico equivalente al isomorfismo gráfico).

Ahora, los comentarios de Joshua Grochow indican que no tuve éxito al explicar la importancia conceptual de las piezas faltantes del problema del isomorfismo de cuerdas. Para estructuras infinitas, puede ser más fácil apreciar que un isomorfismo válido no solo debe preservar la estructura dada, sino también pertenecer a una categoría apropiada de funciones (por ejemplo, la categoría de funciones continuas). Para estructuras finitas, el fenómeno análogo ocurre principalmente para estructuras de cociente, donde la categoría apropiada de funciones debería ser compatible con los cocientes dados. El material de Johnson es un ejemplo típico de tales cocientes, por ejemplo, la lógica de partición está trabajando sobre los subconjuntos de dos elementos de algún conjunto base. También tenga en cuenta que restringir la categoría permitida para los isomorfismos a menudo facilita el problema de prueba de isomorfismo,

El problema con las generalizaciones del problema del isomorfismo gráfico es dónde detenerse. ¿Por qué no generalizar tanto como para abarcar el problema del isomorfismo del grupo de permutación? Esta pregunta es realmente difícil, ya que muchos resultados no triviales para el isomorfismo gráfico probablemente se trasladarán también al isomorfismo del grupo de permutación. Pero aquí se siente más razonable tratar la teoría del grupo de permutación computacional como un tema en sí mismo, incluso si de hecho tiene una estrecha conexión con el problema del isomorfismo gráfico.