Hace 4 años | Por robustiano a elpais.com
Publicado hace 4 años por robustiano a elpais.com

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.

Comentarios

Frankss

#1 Correcto, por eso era una conjetura y no una demostración.

r

#3 te corrijo: por eso era una conjetura y no un teorema (sin haber leído la noticia)

Frankss

#34 Un teorema es demostrable formalmente.

r

#35 pero un teorema no es una demostración


Na. Olvídalo. Que tenía ganas de tocar un poco las narices

AlexCremento

#1 ¿Y? Cualquiera que sepa un poco de matemáticas sabe eso.

RHnegativo

#7 A mi me hablas en cristiano

#12 Lo mismo he pensado

RobertoConde

#7 "Suppose you’re a music teacher who wants to find good duet pairings for the fifth grade concert. You could make a graph whose nodes are the students, with a link between each pair who get along well. And you could make a second graph in which each node is a different musical instrument, with a link between two instruments if you have sheet music for a duet that features them. The tensor product of these two graphs would have one node for each possible pairing of a student and an instrument (say, Alicia on the trombone), and two nodes will be linked whenever the two students in question work well together and the two instruments are compatible."
clap clap clap

RobertoConde

#14 En español:
"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:

RobertoConde

#26 De trabajo para casa: demostrar, coloreando todos los grafos con el mínimo de colores, que en el ejemplo se cumple la conjetura de Hedetniemi.

r

#27 En el ejemplo son dos colores, no?

En el contraejemplo del ruso cada grafo tiene 4^100 nodos para probar que se puede hacer con menos.

#RussianFacts

RobertoConde

#32 No sé, no soi sientífico. Pero son dos.

Top_Banana

#7 Eso en mi barrio es pelea!

EspañoI

Esto es una pasada de descubrimiento, descubrir una propiedad nueva en los grafos puede suponer un avance enorme en inteligencia artificial.

Estoy deseando echar un ojo al articulo!

D

#9 Las redes neuronales ya están un poquitet pasadas de moda para emocionarse con ellas. No son ya muy diferentes a hacer un curso de Word y ofimática allá por los 90.

E

#17 Que va, ahora están otra vez de moda con todo lo de Deep Learning.

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

D

#18 Esas ya llevan unos añitos. Que sean populares en empresas de "tecnología punta" no las hace menos aburridas y vistas.

D

#23 No es lo mismo inventar o desarrollar las redes neuronales, que inventar o desarrollar aplicaciones a dichas redes. Y sí, ahora está de moda usar redes neuronales para un montón de cosas distintas.

l

#23 hombre las GAN son del 2014, pocos añitos me parecen

EspañoI

#17 tanto es así que hoy día se llevan como tres asignaturas en los grados de informática y matemáticas

D

#20 Igual que POO, Cálculo y tantas otras.

Tampoco pasa nada, yo también me emocionaba con el Wordpad en su época. Ánimo.

EspañoI

#22 yo soy de la época del wordpad. Estoy en el lado de los profes.

D

#39 Entonces respect for you.

EspañoI

#50 El respecto es mutuo.

A

#22 ¿El cálculo también está pasado de moda? ¡Valiente símil!

D

#49 El cálculo también es una asignatura, no que esté pasado de moda. Pero bueno, ese debate ya es de ayer. Hoy, helado.

fcruz

#17 lo que tiene hablar sin tener ni idea

D

#21 Ea, ea. Ya pasó.

sorrillo

#9 No acabo de ver la aportación práctica.

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.

EspañoI

#25 creo que #36 lo explica mucho mejor de lo que yo podría.

EspañoI

#25 En mi opinión hay una conclusión muy importante :

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

Maelstrom

#5 Es lo que tienen los contraejemplos, si la conjetura no exige demasiadas condiciones dentro de unos conceptos ya de por sí oscuros (no estamos hablando de grupos gigantescos de Lie).

box3d

#4 y para informáticos en general.
Si hay grafo hay algiritmo que se beneficia.

j

#4 ¿Cómo un algoritmo? Ecuación ya pensada, determinada, calculada, constante en su disposición. Puede interferir en el desarrollo de la inteligencia artificial (que es no constante y consiste en desarrollarse, calcularse y determinarse como cualquier otra inteligencia).

Acido

#4
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.

y

#30 hombre utilidades tiene muchísimas porque hasta antes de la demostración se daba por hecho que si se cumplía. Si hubiera una conjetura que dijera que se puede colgar un piano de cola del techo con un hilo del grosor de un cabello humano todo el mundo guardaría sus pianos de cola colgando del techo encima del sofá y se sentaría debajo tan tranquilamente, que alguien demuestre que en una determinada circunstancia el piano se cae tú si quieres sigue tranquilito en el sofá que yo o cambio el sofá de sitio o guardo el piano en otro lado. Ahora aplícalo a casos prácticos donde una vez encontrado el punto más óptimo según el teorema han dejado de buscar si se podía optimizar más porque según la conjetura es imposible

EspañoI

#30 de hecho se ha descubierto!

Bajo determinadas circunstancias, un grafo producto tensorial G.H tiene una solución más eficiente que sus grafos de origen de forma independiente.

Acido

#40 No comprendo de qué manera eso que acabas de decir responde a mi comentario #30

¿Puedes explicarlo un poco más?

EspañoI

#42 me refiero a que está claro que el paper ha definido una nueva propiedad de los grafos.

Acido

#43
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.

EspañoI

#44 Exacto. Existe un parametro llamado arista-coloracion, que esta ligado al grado maximo de un grafo. Si de repente encontramos una manera de transformar un grafo de forma que se reduce su grado, optimiza la resolucion.

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.

Acido

#45

"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?

EspañoI

#47 No entiendo a que tiene que ver el isomorfismo aquí, salvo que estés pegándome un vacile, pero en todo caso un grafo isomorfo tiene una solución determinista,por lo que no está sujeto a conjeturas.
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.

C

#47 Me suena que es NP-Completo y eso significa que todos los problemas NP son reducibles a ese. Hablo de memoria.

EspañoI

#44 Añado, los problemas de colores tienen dos aplicaciones practicas muy relevantes, la asignacion de registros en los procesadores, y la optimizacion (poda) de redes neuronales y redes GAN.

D

what a Shit

Peachembela

no entendí