• Logo Biblioteca de la Universidad de Sevilla
  • Páginas

  • Categorías

  • RSS GME RSS

    • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.
  • Archivo de MATBUS

  • Comentarios recientes

    Melanicastillo en Sofía XT, una web para mejorar…
    Nahomi Lucero Azuara… en Nahomi Lucero Azuara, de Tamau…
    La Guía de Matemátic… en La Guía de Matemáticas cumple…
  • Escribe tu dirección de correo electrónico para suscribirte a este blog, y recibir notificaciones de nuevos mensajes por correo.

    Únete a otros 124 seguidores

Yaroslav Shitov, el matemático ruso de 30 años que refutó una conjetura no resuelta en medio siglo

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.

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.

¿Es cierto que 4 colores son suficientes para pintar cualquier mapa sin que ningún país vecino tenga el mismo color? ¿Y por qué importa?

Resolver esa primera pregunta (si, dada esa condición, cuatro colores eran suficientes para colorear cualquier mapa) tomó más de un siglo.

Grafo

Esto tiene múltiples aplicaciones. Lo emplean empresas de publicidad para localizar a los influencers en la redes sociales. O se usa para asignar tareas en una fábrica.

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 precisan.

Si alguien demostrase 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.

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 1 millón de dólares a quien pueda resolver alguno de ellos.

“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.

Los productos tensoriales son grafos hechos combinando dos grafos distintos (G y H) de una forma concreta.

En 1966 el profesor 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.

No obstante, Shitov 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 pondría de manifiesto que la conjetura de Hedetniemi es falsa.

Fuente:

https://www.bbc.com/mundo/noticias-48909518

A %d blogueros les gusta esto: