Casi coincidiendo con su 30 cumpleaños (fue el pasado 3 de junio), el nombre de Yaroslav Shitov ha aparecido en buena parte de la prensa mundial. Este matemático ruso ha probado que una conjetura con más de medio siglo de vida sobre un problema de teoría de grafos es falsa, dando un contraejemplo, es decir, aportando un caso en el que no se cumple lo que la conjetura predecía que sucedía siempre.
|
etiquetas: matemáticas , contraejemplos , teoría de grafos , coloreado de grafos 
conjetura
Del lat. coniectūra.
1. f. Juicio que se forma de algo por indicios u observaciones.
(...)
demostración
Del lat. demonstratio, -ōnis.
(...)
5. f. Fil. Comprobación, por hechos ciertos o experimentos repetidos, de un principio o de una teoría.
Diccionario de la RAE
Estoy deseando echar un ojo al articulo!
No llega a dos páginas y media.
Dados dos grafos G y H, el número de colores necesario para colorear el grafo producto tensorial G X H es el menor de los colores necesarios para colorear G y H. Y el contraejemplo ha sido encontrar dos grafos G y H tales que su producto tensorial necesita menos colores que los requeridos para colorear tanto G como H
Para una explicación sobre grafos tensoriales en relación a esta conjetura: www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theor
Si hay grafo hay algiritmo que se beneficia.
#8 en este caso concreto es incluso mas relevante, porque el podado de redes neuronales tiene un calculo muy parecido al problema de los colores. Esto es MUY bueno, y me hace pensar como un tio de 30 años puede ser tan bueno en matemáticas hoy día.
PD. Soy de Ciencias de la Computacion, no puedo evitarlo.
<<Por tanto, si encontramos un algoritmo que resuelva de forma eficiente el problema de colorear grafos (con una cantidad de operaciones menor que un cantidad relacionada con el número de vértices del grafo), podemos ir al instituto Clay y reclamar un millón de dólares, porque habremos demostrado que P es distinto a NP, y con ello uno de los célebres problemas del milenio y que llevan asignado ese premio. Si alguno de los lectores tiene el algoritmo pero no entiende por qué implica que P es distinto de NP, los autores de este artículo se brindan a aclarar las dudas. Compartiendo parte del premio, claro está.>>
Primero, para que sea eficiente, la cantidad de opciones tiene que ser menor que un número relacionado polinomicamente con el número de vertices (o de aristas)... no te puedes saltar el polinomicamente, si no 2^|V| también vale y el algoritmo sería exponencial.
Segundo, lo que estarías probando sería que P = NP, ya que estarías encontrado un algoritmo polinomial (eficiente) para un problema NP-Completo (representante universal de la clase NP).
Por ejemplo, tienes las redes neuronales profundas (DNN) y las redes neuronales adversariales (GAN). Son dos de las técnicas más populares actualmente en investigación y en empresas de tecnología "punta".
Ha encontrado un caso particular para el cual no se da lo que proponía la conjetura. Un ejemplo de un caso particular a priori no parece especialmente útil para aplicarlo de forma general.
Si alguien estaba basándose en esa conjetura para operar lo que debe hacer es seguir como está si esos casos particulares son demasiado excepcionales para ser relevantes o directamente dejar de usarlo. Lo cual no parece a priori un avance si no más bien un retroceso.
Y si por contra no se estaban basando en esa conjetura no tiene sentido hacerlo ahora.
Otra historia sería que a partir de este caso particular alguien generalizase algo diferente y útil, pero no parece que sea lo que aporta este meneo.
"Supón que eres un profesor de música que quiere encontrar buen emparejamientos para duetos en un concierto de alumnos de quinto curso. Podrías hacer un grafo cuyos vértices son los estudiantes, con una arista entre cada pareja que se lleva bien. Y podrías hacer un segundo grafo en el que cada vértice es un instrumento musical diferente, con una arista conectando dos instrumentos si tienes una partitura de dueto para esos dos instrumentos. El producto tensorial de esos dos grafos tendría un vértice por cada posible emparejamiento de un estudiante y un instrumento (por ejemplo, Alicia al trombón), y dos vértices conectados siempre que los dos estudiantes en cuestión se lleven bien y los dos instrumentos sean compatibles"
En matrices:
Le va a tocar a otro.
En ejempleño:
Querrás decir descubrir que los grafos NO tienen una propiedad...
No se qué aplicaciones puede tener descubrir que una posible propiedad en realidad no se cumple siempre.
En el contraejemplo del ruso cada grafo tiene 4^100 nodos para probar que se puede hacer con menos.
#RussianFacts
Na. Olvídalo. Que tenía ganas de tocar un poco las narices
Bajo determinadas circunstancias, un grafo producto tensorial G.H tiene una solución más eficiente que sus grafos de origen de forma independiente.
Bajo determinadas circunstancias, un grafo producto tensorial G.H tiene una solución más eficiente que sus grafos de origen de forma independiente.
Esto significa que puede realizarse una poda de forma más eficaz en un grafo. Los grafos son parte fundamental de la teoría de Algoritmos que gobiernan la computación...
Y el tío lo ha sacado a papel y lápiz, con un método de generación de grafos QUE SIEMPRE cumplirán la propiedad. Es un matemático muy bueno...
¿Puedes explicarlo un poco más?
Ah, claro, la propiedad de no tener la propiedad que se pensaba ¿es eso?
Sigo sin saber qué posibles aplicaciones puede tener... Quizá que hasta ahora se daba por hecho o por supuesto que el número de colores era cierto número y ahora al saber que puede ser menor puede intentarse una solución más óptima.
Si a este descubrimiento, le siguiera un procedimiento para generalizar la reduccion de grado de un grafo, estariamos ante un via para hallar la solucion a la conjetura P=NP, puesto que un grafo de colores es un problema NP.
"estariamos ante un via para hallar la solucion a la conjetura P=NP, puesto que un grafo de colores es un problema NP."
Pero para eso se necesitaría no solamente que un grafo de colores sea NP sino que todo problema NP pueda reducirse o sea isomorfo a un grafo de colores ¿no te parece?
La conjetura de Hedetniemi propone un escenario distinto.
De todas maneras, aclaro: Todo avance en la teoría de grafos sería una vía de investigación de los problemas NP, NO una solución a los problemas NP. Me temo que hoy día no tenemos herramientas para llegar a ese punto.