Los investigadores en ciencias de la computación de la Universidad de Copenhague y la Universidad Técnica de Dinamarca (DTU) pensaron que faltaban cinco años para resolver un acertijo matemático de la década de 1980. En realidad, y sin saberlo, casi habían resuelto el problema y acababan de revelar gran parte de la solución en un artículo de investigación. La solución podría utilizarse para mejorar los teléfonos y las computadoras del mañana.

Jacob Holm y Eva Rotenberg

Un verdadero desafío para la mente. Así es como se puede describir con seguridad este problema matemático en la disciplina de la teoría de grafos. Dos matemáticos del Departamento de Ciencias de la Computación de la Universidad de Copenhague y DTU ahora han resuelto un problema con el que los más rápidos e inteligentes del mundo han estado luchando desde la década de 1980.

Los dos informáticos, El profesor asistente Jacob Holm de UCPH y la profesora asociada Eva Rotenberg de DTU casi revelaron su solución en el verano de 2019, después de enviar un artículo de investigación que se convirtió en el precursor del artículo en el que finalmente resolvieron el acertijo matemático.

"Casi nos habíamos dado por vencidos en conseguir la última pieza y resolver el acertijo. Pensamos que teníamos un resultado menor, uno que fue interesante, pero de ninguna manera resolvió el problema. Supusimos que habría otros cinco años de trabajo, a lo mejor, antes de que pudiéramos resolver el rompecabezas, "explica Jacob Holm, que es parte de BARC, la sección de algoritmos del Departamento de Ciencias de la Computación de la UCPH.

El problema de las tres utilidades

En 1913, un precursor del acertijo matemático ahora resuelto se publicó en Revista The Strand como "El problema de las tres utilidades". Hizo que los lectores de la revista se rascaran la cabeza y reflexionaran. En el problema cada una de las tres cabañas debe tener agua, gas y electricidad, mientras que las "líneas" entre las casas y el agua, la electricidad y el gas no pueden cruzarse, lo cual no es posible.

Una solución entre líneas

Simplemente pon, el acertijo trata de cómo conectar varios puntos en un gráfico sin permitir que las líneas que los conectan se crucen. Y cómo, con un cálculo matemático, un algoritmo, puede realizar cambios en una extensa "red de gráficos" para asegurarse de que ninguna línea se cruce sin tener que empezar de nuevo. Propiedades que se pueden utilizar para, entre otras cosas, la construcción de inmensas redes de carreteras o las diminutas entrañas de las computadoras, donde los circuitos eléctricos de las placas de circuitos no puedan cruzarse.

Jacob Holm ha estado interesado en el enigma matemático desde 1998, pero la respuesta solo se reveló mientras los dos investigadores estaban leyendo su artículo de investigación ya enviado. Mientras tanto, los investigadores se enteraron de una técnica matemática novedosa que se dieron cuenta de que podía aplicarse al problema.

"Mientras lee nuestro artículo de investigación, de repente nos dimos cuenta de que la solución estaba ante nuestros ojos. Nuestra siguiente reacción fue 'oh no, nos disparamos en el pie y regalamos la solución, ', dice la profesora asociada Eva Rotenberg de DTU.

Acerca de la teoría de grafos

Un gráfico es una construcción muy simple que se utiliza para modelar cosas que se pueden describir como objetos y las conexiones entre ellos. La teoría de grafos es un área de las matemáticas y una herramienta importante en la informática.

En este contexto, Un gráfico se puede ilustrar con un diagrama que consta de varios puntos (nodos, vértices) asociados con una serie de líneas (bordes). Cada borde se ilustra como una línea (o pieza curva) con nodos como sus dos puntos finales.

Sobre la solucion

Hay dos tipos de actualizaciones en los gráficos dinámicos:uno puede eliminar un borde y puede insertar un nuevo borde. Estas dos operaciones las debe realizar el usuario, mientras que un algoritmo realiza un seguimiento del dibujo de la red en todo momento. Este es el algoritmo para el que los investigadores han encontrado la receta.

Podría usarse para electrónica informática

Fue entonces cuando los dos investigadores se pusieron ocupados escribiendo el trabajo de investigación y atando cabos sueltos para resolver el enigma en el que Holm había estado trabajando de forma intermitente desde 1998.

"Trabajamos en el artículo sin parar, durante cinco a seis semanas. Y, terminó llenando más de 80 páginas, "dice Eva Rotenberg.

Afortunadamente, nadie se les adelantó en la solución y los dos investigadores pudieron presentar sus resultados en las principales conferencias teóricas de informática, que estaban destinados a celebrarse en Chicago, pero terminó siendo retenido virtualmente.

Entonces, ¿Para qué se puede utilizar la solución a este acertijo matemático? Los dos investigadores no lo saben con certeza, pero tienen algunas sugerencias.

"Nuestra investigación es investigación básica, por lo que rara vez sabemos para qué se utilizará. Incluso desde el principio encontramos aplicaciones difíciles de imaginar, "dice Jacob Holm, quien agrega, "El diseño de microchips y placas de circuito, encontrado en toda la electrónica, podría ser un área donde nuestro resultado termine siendo utilizado. Al dibujar cables en una placa de circuito, nunca deben cruzarse. De lo contrario, se producirán cortocircuitos. Lo mismo se aplica a los microchips, que contienen millones de transistores y para los cuales se debe tener un dibujo gráfico ".