Algorítmica y complejidad computacional. Isomorfismo de grafos en tiempo cuasi-polinómico: el artículo.

Finalmente se ha publicado en Arxiv el esperado artículo de Babai. Recordamos que Arxiv no es una revista con revisión con pares. Seguramente habrá comentarios en breve de expertos en sus respectivos blogs. Por falta de tiempo nosotros no lo vamos a leer, aunque en diagonal vemos cosas muy interesantes como las que se muestran en el siguiente extracto.

Extracto. 

Luks’s method meets a barrier when it encounters large primitive permutation groups without well-behaved subgroups of small index. By a 1981 result of Cameron [Cam81] these barrier groups are the “Johnson goups” (symmetric or alternating groups in their induced action on t-tuples). This much has been known for more than 35 years. Our contribution is in breaking this symmetry. 

Título. Graph Isomorphism in Quasipolynomial Time

Abstract.

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial (exp (log n) O(1) ) time. The best previous bound for GI was exp(O( √ n log n)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp(Oe( √ n)), where n is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks’s SI framework and attacks the barrier configurations for Luks’s algorithm by group theoretic “local certificates” and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning.

P.s. todo sigue igual con respecto a la problemática con el buscador de Google. No han ni reaccionado a la última acción realizada con su plataforma automática de resolución de problemas ni contestado a la carta. Obviamente no les he enviado la carta física a su sede de EEUU y es muy posible que incluso enviandosela no hagan nada tampoco. No obstante por causas ajenas a mi voluntad he eliminado algunos contenidos del blog relacionados con este tema. Ya me está perjudicando lo suficiente como para hacerlo más perjudicial.

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 WordPress.com

Estás comentando usando tu cuenta de WordPress.com. 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 )

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: