Complejidad computacional. Isomorfismo de grafos en tiempo cuasi-polinómico.

El resultado por lo visto es de Babai. ¿ Podía haber obtenido este resultado alguien que no fuese húngaro ? :-).

Recordamos que  Quasi-polynomial time algorithms are algorithms which run slower than polynomial time, yet not so slow as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is 2^{O((\log n)^c)} for some fixed c. The best-known classical algorithm for integer factorization, the general number field sieve, which runs in time about 2^{\tilde{O}(n^{1/3})} isnot quasi-polynomial since the running time cannot be expressed as 2^{O((\log n)^c)} for some fixed c. If the constant “c” in the definition of quasi-polynomial time algorithms is equal to 1, we get a polynomial time algorithm, and if it is less than 1, we get a sub-linear time algorithm.

La mejor cuota superior anterior para este problema era tiempo subexponencial:  The previous fastest algorithm to decide whether two n-vertex graphs G and H are isomorphic—by Babai and Luks, back in 1983—ran in exp(√(n log n)) time

Las consecuencias de este resultado con respecto a la teoría de la complejidad computacional, si no recuerdo mal son, ninguna. No es que fuera esperado pero tampoco está en contradicción con ninguna de las conjeturas habituales. Seguramente el lector se habrá realizado una pregunta sobre la relación entre problemas NP-completos y la clase  QP (Quasi-polynomial) cuya respuesta puede encontrar aquí. Resulta que este tema está relacionado con otro que nos ha interesado mucho: la relación entre EXP y NEXP.


DTIME(npolylogn) is known as QP (quasi-polynomial).

It is widely believed that NP⊂/QP, although it is a stronger statement than PNP.

Some common conjectures, such as the Exponential Time Hypothesis imply NP⊂/QP.


Another good reason to believe NPQP is that NPQP implies EXP=NEXP, and the latter is thought highly unlikely. This implication can be proved by a padding argument, see, e.g., in the proof of Proposition 2 in the following paper:

H. Buhrman and S. Homer, “Superpolynomial circuits, almost sparse oracles and the exponential hierarchy,” Foundations of Software Technology and Theoretical Computer Science, Springer LNCS Vol. 652, 1992, pp. 116-127, pdf.

I think, any violation of ETH probably implies some collapse at a higher level. I guess, the level depends on “how strongly” the ETH is violated, stronger violations yielding more dramatic collapses. As pointed out in the answer, the strong ETH violation of NPQPimplies EXP=NEXP. If we take a milder violation, such as assuming that NP is in a subexponential class larger than QP, then the collapse is probably shifted upwards (e.g., to double exponential classes or even higher)

I was asking about a direct implication either way between ETH and EXPNEXP. We now have two answers – ETH implies NPQP and NEXPEXP implies NPQP – and I was curious if one was a consequence of the other.

On another note, it is quite interesting that ETH violations can yield not only collapses, but also separations, in terms of circuit lower bounds.

En alguna ocasión hace bastante tiempo hemos publicado alguna entrada sobre este problema u otros relacionados, como el de isomorfismo  de grupos. Concretamente, inspirados por una tesis de 2009 titulada Efficient algorithms for graph isomorphism testing en la que nos comentan sobre cuales son las familias de grafos más complicadas para cualquier algoritmo de GI hicimos una entrada específica sobre estas familias.

El autor ha publicado mucho en temas relacionados de alguna manera con nuestra propia investigación. Un ejemplo: Anterior de los  mismos autores. L. Babai and A. Seress. On the diameter of Cayley graphs of the symmetric group. J. Combin. Theory Ser. A, 49(1):175–179, 1988.

Nos preguntamos que técnicas habrá utilizado para mejorar la cota superior de este importante problema. Pronto lo sabremos. El abstract de la presentación que va a hacer en breve nos da unas pistas.

  • Title: Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time (Combinatorics and TCS seminar)
    When: Tue Nov 10, 2015 3pm to 4pm  CST
    Where: Ry 251

    We outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylog n)) time.  

Actualización 6 de  noviembre 2015. 

Babai va a dar una segunda conferencia dos  días después.

Title: Laszlo Babai (UChicago): A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism problem
When: Thu Nov 12, 2015 4:30pm to 5:30pm  CST
Where: Eckhart 203

Description: The Graph Isomorphism (GI) problem asks, given two graphs with n vertices, decide whether or not they are isomorphic. This is a classical algorithmic problem that has received considerable attention in the theory of computing because of its unsettled complexity status within the P/NP theory.

The asymptotic theory of finite permutation groups plays a central role in the study of this algorithmic problem, thanks especially to Luks’s seminal 1981 paper. In 1983, Luks proved that the GI problem can be solved in exp(sqrt{n log n}) steps. This remained the state of the art for over three decades.

The speaker’s recent result brings this upper bound down to quasipolynomial, i.e., exp((log n)^c). In the talk I will outline some elementary (modulo Schreier’s hypothesis) group theoretic results that are at the heart of this development, and try to give some indication of their relevance to the algorithmic problem.

Actualización 11 de noviembre.

La primera conferencia fue ayer y no hay mucha información de momento. Algún asistente la ha twiteado pero este no es el mejor medio para comprender los métodos. O quizás sí para los iniciados. He leído la secuencia de twits y debido a mi desconocimiento de este tema no sabría decir lo que es nuevo. Habla: del grupo simétrico, alternado, de los grafos de Johnson, de un reducción de isomorfismo de grafos al problema de isomorfismo de strings; utiliza de manera elemental la clasificación de grupos finitos etc…Aparentemente el algoritmo es del tipo divide y vencerás: empieza con un grafo regular en el que se individualizan un número polylog de vértices. Luego se obtienen tres casos y a cada uno de ellos se le da un tratamiento. ¿ Confuso ? Sin duda. Puedo seguir partes pero la narrativa completa se me escapa. Hay que esperar. 

Hay una tercera conferencia en noviembre.

Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The “Split-or-Johnson routine” (Combinatorics and TCS seminar)

In this second talk of the series we present the details of the canonical partitioning algorithms required for the master algorithm. This is a stand-alone module and can be understood without knowledge of the master algorithm outlined in the first talk. Basic familiarity with discrete structures such as undirected and directed graphs, bipartite graphs, hypergraphs will be assumed. No group theory beyond the concept of the symmetric group is required.

Y en diciembre hay un seminario sobre este problema en el Schloss Dagstuhl en diciembre de 2015, en el  que participarán los pesos pesados. Quizás la existencia de este seminario le ha estimulado para avanzar en el problema. O quizás ya tenía el resultado y por ello se ha realizado sobre este tema.


While many other computational problems have a canonical community associated with them, resulting in dedicated conferences, the situation for the isomorphism problem is different. This is due to the fact that the background of people working on the isomorphism problem is quite diverse which leads to infrequent encounters at regular conferences or other events.

This diverse landscape manifests itself for example in the following communities:

  • practitioners that implement software around the Graph Isomorphism Problem yielding widely used packages and libraries
  • logicians approaching the Graph Isomorphism Problem with techniques such as descriptive complexity theory, and using the problem to prove lower bounds in several proof systems
  • algorithmic group theorists that drive the approach to the problem via group theory, yielding to date the best known algorithm with respect to worst-case complexity
  • graph theoristsanalyzing the underlying objects from a structural viewpoint solving ever-increasing subcases of the general problem
  • complexity theorists highlighting the special position the Graph Isomorphism Problem takes in the complexity landscape
  • scientists from the area of combinatorial optimization that apply optimization techniques to isomorphism solving (such as semi-definite programming hierarchies) and conversely use isomorphism tools to speed up optimization procedures
  • researchers that apply isomorphism related techniques in and from other areas such as machine learning

The program will include the following five overview talks on topics of great current interest.

  1. Graph indistinguishability through hierarchies of relaxations [Albert Atserias]
  2. Practical aspects of the graph isomorphism problem [Brendan McKay]
  3. Graph isomorphism: the bottlenecks [Laszlo Babai]
  4. Complexity classes and graph isomorphism [Jacobo Toran]
  5. Parameterizations and the graph isomorphism problem [Pascal Schweitzer]

McKay es el autor del algoritmo más rápido desde el punto de vista práctico para este problema, Nauty. Babai en su primera conferencia ha afirmado que su algoritmo es de interés teórico y que a fines prácticos  se seguirá utilizando Nauty.

Fin de actualización. 


Esto de Coset intersection nos suena…a idea abstracta ;-). No tengo claro si este concepto de coset intersection es similar a lo que nosotros hemos  llamado intersección IAS-DAS, clave para la propiedad de entrelazado que a su vez es clave para las propiedades de hamiltonicidad en un Digrafo de Cayley bigenerado. A tales efectos recordamos que el concepto de IAS no es equivalente al de Coset, aunque lo contiene. Y recordamos que nuestro objeto básico es el par de generadores y el dígrafo  que generan, algunos de sus subdigrafos y la intersección entre estos. No nos interesan tanto las técnicas de teoría de grupos. Estoy averiguando esto para ver si tengo que revisar la redacción de las nuevas claims que voy a presentar.

El prólogo e indice al libro de Hoffman de 1982 dónde se presentan estos problemas.

Un libro dónde explican los conceptos  de teoría de grupos  (incluido el de coset) de manera intuitiva. El objetivo es explicar las aplicaciones de la teoría de grupos a la física.

Más de lo mismo, sobre cosets, con ejemplos gráficos.


Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )


Conectando a %s

A %d blogueros les gusta esto: