La complejidad del isomorfismo de grafos es cuasipolinómica en tiempo

Por Francisco R. Villatoro, el 27 enero, 2017. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Noticias • Personajes • Science ✎ 26

Dibujo20151210 Graph Isomorphism in Quasipolynomial Time seminar lecture by Laszlo Babai university chicago

László Babai (Premio Knuth 2015) afirmó en diciembre de 2015 haber demostrado que la complejidad algorítmica del problema del isomorfismo de grafos es cuasipolinómica (LCMF, 11 Dic 2015). El matemático peruano Harald A. Helfgott ha verificado la demostración en detalle y afirma que es correcta. El 14 de enero impartió una charla Bourbaki en el Instituto Henri Poincaré de París. La importancia del trabajo de Babai (65 años), es que abre la esperanza a que matemáticos más jóvenes, usando sus nuevas ideas, logren avances relevantes sobre el problema P vs NP. El isomorfismo de grafos es un problema NP, que no sabemos si es NP-completo; si estuviera en P sería algo revolucionario.

Helfgott encontró un error en el cálculo de la complejidad del nuevo algoritmo de Babai. Como resultado parecía que no lograba superar la barrera subexponencial. Sin embargo, Babai logró resolver el problema en su algoritmo. Sustituyó, tras unos días de trabajo, una rutina llamada «Split-or-Johnson» (que causaba el problema) por una versión modificada. Helfgott impartió su charla Bourbaki afirmando que la solución de Babai resuelve el problema que encontró. Por supuesto, el trabajo de Babai todavía no ha pasado por revisión por pares. Habrá que estar al tanto de lo que opinan otros expertos. Pero todo pinta muy bien para Babai.

La explicación de Helfgott de la demostración de Babai la puedes disfrutar en Harald Andrés Helfgott, «Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman…),» arXiv:1701.04372 [math.GR]. Recuerda que el posible error se anunció en Helfgott, «Graph isomorphism in subexponential time,» The value of the variable, 04 Jan 2017, y en Babai, «Graph Isomorphism update,» Univ. Chicago, 04 Jan 2017. La solución del error aparece en Babai, «Update: quasipolynomial claim restored,» Univ. Chicago, 09 Jan 2017.

Quizás te interese consultar algunas fuentes adicionales sobre el trabajo de Babai: Tom Simonite, «Un informático teórico logra «el descubrimiento de la década» en su campo,» MIT Tech. Rev. 17 Nov 2015; Kanijo, «Un avance en la teoría de grafos entusiasma a los matemáticos», Ciencia Kanija, 24 Nov 2015; Pedro Donaire, «Un nuevo algoritmo que rompe 30 años de estancamiento», Bitnavegantes, 14 Dic 2015; Pablo Estrada, «Sacudiendo el mundo de los algoritmos», Bit y Byte, 20 Dic 2015; etc.

[PS 27 Ene 2017] Esta entrada participa en la Edición 7.X del Carnaval de Matemáticas cuyo anfitrión es el Blog del IMUS. Recuerda que se puede participar hasta el 29 enero. Basta escribir una entrada sobre matemáticas y anunciarlo por Twitter con la etiqueta #CarnaMat7x y una mención a la cuenta @IMUS y a @CarnaMat.



26 Comentarios

          1. Francis, yo pensaba que la Paradoja de Levinthal estaba también presente incluso aunque se trate con física cuántica…es decir, que un mecanismo cuántico tampoco iba a salvar el aparentemente imposible velocidad con la que se pliegan…entiendo que no es así…

        1. Pelau, ninguna reseñable. La complejidad algorítmica cuántica y la clásica no tienen relación directa. Por ejemplo, la mayoría de los expertos creen que hay problemas BQP que no están en NP. No hay que olvidar que en gravedad emergente lo natural son los problemas más allá de PSPACE, en EXPTIME. La pecata minuta de P=NP es irrelevante en las propuestas de Susskind y cía.

          1. Gracias, Francis. En su momento, alguien que ya no comenta en el blog (no con ese nickname al menos) posteó una info que me había dejado con la duda. Saludos.

          2. Comentario muy interesante.

            ¿Puedo preguntar por qué razón los problemas «más allá» de PSPACE y PTIME son relevantes en gravedad emergente?.

            Intuitivamente imagino que la razón es que si uno acepta que la gravedad emerge entonces el espaciotiempo lo hace (¿cierto?) y si admitimos que el universo es una forma de computación entonces habría que definir una clase de complejidad que no hiciese alusión a los recursos «tiempo y espacio».

      1. La seguridad sería un problema, pero habría mucho más que uno no sabe si sería para bien o para mal… El salto sería brutal: predicciones de big data, bolsa, optimización…comenzaría una guerra algorítmica…bufff, da miedo.

        1. Pedro, la seguridad no sería ningún problema. Ya hay algoritmos de cifrado que evitan el problema que supone P=NP. Los algoritmos actuales serían obsoletos y habría que usar nuevos algoritmos. ¿Recuerdas el efecto 2000? Pues pasaría lo mismo, … ¿tuviste miedo por el efecto 2000?

          1. Pues yo sí. No del supuesto colapso administrativo y financiero global. Tuve miedo de que todos los árboles del planeta terminaran en las imprentas para dar abasto a tanta chorrada: marcapasos deteniéndose, aviones cayendo de los cielos, hornos microondas asesinos, gatos y perros amigos… ¡El Fin Del Mundo! 🙂

          2. Pero lo que digo no es tanto por la seguridad (y ya con lo que me cuentas, pues tranquilo al 100%), como tampoco me preocupó el 2000 (de hecho soy de aquellos que les tocó currar como burros modificando software viejuno, porque como siempre, en España, los proyectos se adjudicaron a ultimísima hora) pero… ¿os dais cuenta del salto? no sé, a lo mejor me como demasiado la cabeza, pero ¿lo habéis pensado? o sea, está claro que los algoritmos actuales para invertir en bolsa, para buscar el camino más óptimo, la mejor estrategia…etc, son buenísimos, son brutales, pero de repente pasarían de brutales por usar métodos que les permite quitarse de encima casos , a ser hiperbrutales… veo bondades mil, y veo maldades mil con las que habrá que lidiar muy rápido.

            También me es imposible de imaginar una fórmula secreta para el subset sum problem ¿os imagináis? con la de veces que le he dado vueltas; si hubiera un algoritmo que lo solucionara en un tiempo polinomial, sin necesidad de ir caso a caso, o sin tentativas aproximativas, seguro que yo no lo entendería, seguro que estaría por encima de mis posibilidades, sería magia para mí.

      2. Entonces si existe un algoritmo en tiempo polinomial para el problema de isomorfismos de grafos también se podrían resolver otros problemas np con este algoritmo?

          1. Pero tampoco serviria almenos para resolver otros problemas que se consideren que estén en la clase np intermedia? Después de todo tengo entendido que el problema de isomorfismos no es np completo pero si es np

  1. Francis, …..a manera de off topic, ¿crees que Harold Helffgot pudiera alcanzar todavía la Medalla Fields en el 2018? (tendría -a la fecha del congreso en agosto del 2018- aún 40 años, porque los 41 los cumpliría recién en noviembre). O tendría que resignarse a que sea reconocido al final de su carrera con el Premio Abel (si es que se lo dan). Porque a parte de que se lo merece (demostración de la Conjetura Débil de Goldbach) es un investigador que no se duerme en sus laureles y sigue siendo todo un referente entre los matemáticos de nivel.

    1. ¿Resignarse? , Laudeamus, sinceramente, yo preferiría de todas todas el premio Abel al Fields, estamos hablando de unos 600.000 euros frente a los 10.000 del fields; o el premio Wolf con 100.000. Está claro que el dinero no lo es todo, pero tampoco tengo nada claro por qué los periodistas eligieron el Fields para darle bombo y ornato, y decir «está considerado el Novel», supongo que porque se quiso equiparar en fecha y estatus, pero poco más.

      Por otro lado, un premio como el Fields, cuya finalidad es alentar a los jóvenes a ponerse las pilas y sacar mayor provecho a su años de creatividad, ganarlo in extremis a los 40…pues laudeamus, de nuevo, si yo fuera un fuera de serie y mereciera ser galardonado, preferiría pasar de puntillas y llevarme algo más cuantioso después.

    2. Laudemus, espero equivocarme, pero creo que no. Helffgot lo merece, pero la competencia es muy fuerte. En las listas actuales Helffgot está por encima del puesto 10 y casi seguro los 4 galardonados estarán entre los 10 primeros puestos. Salvo sorpresa de última hora, en mi opinión, Helffgot se quedará sin la Fields. Por supuesto, espero equivocarme.

      1. Si me dicen que mi hijo (que es matemático de profesión de una reconocida universidad americana) a los treintantos años ha logrado demostrar uno de las conjeturas capitales de las matemáticas del siglo XX, llegando incluso a ser corroborado por sus colegas como correcta antes de los 40 y me dicen que dicho logro, no lo catapulta a ser considerado ni entre los 10 primeros candidatos de su generación, apagá y vámonos, este premio no hay por donde cogerlo! le diría que se vaya buscando una segunda profesión,

Deja un comentario