En solo dos páginas y media, un matemático ruso de 30 años desmontó una conjetura matemática que tenía más de 50 años.
Yaroslav Shitov, que trabajó hasta hace poco en el Alta Escuela de Economía de Moscú, sorprendió al mundo de las matemáticas al encontrar un ejemplo que refuta una conjetura sobre un problema de teoría de grafos.
“Un grafo es una estructura matemática muy simple: solo tiene puntos y aristas, que son una comunicación entre dos puntos”, le dice a BBC Mundo Alberto Márquez, quien explicó el descubrimiento recientemente en el blog “Café y teoremas” del diario El País.
Márquez, catedrático de Matemática Aplicada de la Universidad de Sevilla, se quedó sorprendido por la sencillez del trabajo de Shitov, que publicará en septiembre la revista Annals of Mathematics.
Uno de los problemas más estudiados en este campo consiste en encontrar el mínimo número de colores que se pueden dar a los vértices de un grafo para que no haya dos con el mismo color unidos por una arista, lo cual se conoce como número cromático.
“El número cromático es probablemente uno de los más estudiados dentro de la teoría de grafos”, le explica a BBC Mundo Shitov desde Moscú.
“Se remonta al problema de la conjetura de los cuatro colores. Si tienes un mapa de los países del mundo, puedes utilizar cuatro colores y colorearlos de forma que no haya dos países vecinos con el mismo color”, dice Shitov.
“Esta fue la motivación inicial de por qué la gente estudió este tema del número cromático”.
Resolver esa primera pregunta (si, dada esa condición, cuatro colores eran suficientes para colorear cualquier mapa) tomó más de un siglo.
Esto tiene múltiples aplicaciones. “Lo utilizan empresas de publicidad para localizar a los influencers en la redes sociales”, ejemplifica Márquez. O para asignar tareas en una fábrica.
También sirve para cosas más banales como organizar las mesas de una boda evitando que dos personas que no se soportan tengan que sentarse juntas.
Dado un grafo, no existe o no se conoce ningún algoritmo que resuelva de forma eficiente cuál es el mínimo número de colores que se necesitan.
“Si alguien demostrara que existe ese algoritmo o que no existe, resolveríamos uno de los problemas más famosos del milenio: si P es igual o distinto que NP”, asegura Márquez.
Este es uno de los siete problemas del milenio publicados en el año 2000 por el Instituto Clay de Matemáticas de Peterborough (Estados Unidos) y para los que ofrece US$1 millón a quien pueda resolver alguno de ellos.
Hasta ahora, solo uno ha sido resuelto. El responsable de tal hazaña fue el ruso Grigori Perelman, quien nunca recogió el premio.
El problema de “P versus NP”
“P versus NP” aspira a demostrar o refutar la creencia de que hay problemas para los que, por su complejidad, es más difícil encontrarles una solución que comprobar si esa solución es correcta.
Los problemas P (polinómicos) son los que se pueden resolver en un tiempo razonable. Los problemas NP (no deterministas en tiempo polinómico) son aquellos que, aunque sea difícil encontrarles solución, una vez hallada se puede comprobar en un tiempo razonable que es correcta.
Si se puede encontrar fácilmente una solución, esta también se podrá verificar de manera sencilla, por lo que todo problema P es también NP.
Lo que se desconoce es si hay algún problema NP que no sea P. Los expertos confían en que así sea, pero de momento nadie ha sido capaz de demostrarlo.
“Como este problema es tan complicado, lo que se intenta es dar fórmulas que te relacionen el mínimo número de colores que se necesitan para un grafo con otro grafo. Entonces hay una operación de grafos que se llama producto tensorial”, afirma Márquez.
Los productos tensoriales son grafos hechos combinando dos grafos distintos (G y H) de una forma concreta.
En 1966 el profesor ahora jubilado Stephen Hedetniemi conjeturó en su tesis doctoral que dados dos grafos G y H, el número de colores necesario para colorear el grafo producto tensorial GXH es el menor de los colores necesarios para colorear G y H.
Hasta ahora, muchos creían que esta conjetura era cierta, porque todo lo que se había comprobado la verificaba.
“Yo personalmente pensé que la conjetura debía ser verdadera, porque mucha gente inteligente la había estudiado y debía haber encontrado un contraejemplo” si hubiera existido, le dijo a Quanta Magazine Anthony Bonato, profesor de matemáticas de la Universidad Ryerson de Toronto.
Y, según Márquez, había en marcha muchos esfuerzos para intentar demostrarlo.
Shitov, sin embargo, ha encontrado dos grafos G y H tales que su producto tensorial necesita menos colores que los requeridos para colorear tanto G como H, lo cual demuestra que la conjetura de Hedetniemi es falsa.
“Tras un tiempo me di cuenta de que la conjetura debía ser falsa y que tenía que trabajar en encontrar contraejemplos”, explica Shitov, lo cual le llevó aproximadamente un año (durante el que también hizo otras cosas, cuenta).
La prueba es “básica, pero ingeniosa”, declaró a Quantum Magazine Pavol Hell, de la Universidad Simon Fraser de Canadá.
“Continuamente se desmontan o demuestran conjeturas”, dice Márquez. “Lo que pasa es que casos como este en que todo el mundo está convencido que debe ser cierta, es llamativo”.
Márquez agrega que también tiene el mérito de la originalidad “porque describe la existencia de grafos que tienen muchísimos más vértices que el número de partículas elementales que hay en el universo”.
Hedetniemi, por su parte, se declaró “absolutamente encantado” de que se resuelva su conjetura después de tanto tiempo.
La prueba de Shitov, escribió en un correo a Quanta, “tiene cierta elegancia, simplicidad y calidad definitoria”.
Fuente: BBC