jueves, 01 de diciembre de 2022
Editoriales

Ciencia en los medios: Viajante de Comercio

Los fascinantes problemas no resueltos de la Matemática

Publicado en Página 12. 10/03/2022

Por Adrián Paenza

 

 

Es curioso porque la percepción que tiene la mayoría de la gente (según mi experiencia) es que la matemática ya está toda hecha, descubierta, inventada y se supone que hay libros que contienen toda la información, y en el caso de que uno necesite entender o aplicar algún resultado o teoría, todo lo que tiene que hacer es ir y buscar en el libro adecuado … ¡y listo! Algo así como si fuera una ciencia muerta. Pensar así es estar totalmente alejado de la realidad. La matemática está “vivita y coleando”, tiene una enorme cantidad de problemas irresueltos (abiertos), cuya solución se desconoce, y muchos llevan siglos sin que nadie hubiera podido hacer un aporte que aclarara -al menos en parte- qué camino elegir para encontrar la respuesta.

Por supuesto, muchísimos de los problemas son difíciles de plantear o de entender, salvo que uno sea especialista en el tema. En medicina, por ejemplo, es fácil comprender qué significa que una persona sufra del mal de Alzheimer, pero aún estamos lejos de resolver la situación. Se entiende el enunciado, la descripción del problema en sí mismo, es observable, pero se desconoce aún como erradicar cualquier variante de demencia.

En cuanto a la matemática, las situaciones irresueltas no conllevan la misma familiaridad ni nos son tan sencillos de entender como este ejemplo de la medicina. Sin embargo, hay algunas excepciones. Hace 16 años, en este mismo diario[1], escribí en la contratapa uno de los problemas más famosos -que todavía no tiene un siglo de vida- muy fácil de enunciar y comprender, pero cuya solución aún se ignora: “El Problema del Viajante de Comercio”. Un brevísimo resumen que no le llevará mucho esfuerzo en seguir.

Una persona tiene que recorrer un cierto número de ciudades que están todas interconectadas (pueden ser rutas, carreteras o por avión). Es decir, siempre se puede ir de una hacia otra en cualquier dirección. Además, otro dato que se tiene, es cuánto hay que pagar para ir de una a otra. A los efectos prácticos, voy a suponer que viajar desde la ciudad A hasta la ciudad B, sale lo mismo que viajar desde B hasta A. El problema consiste en construir un itinerario que pase por todas las ciudades una sola vez, y que termine en el mismo lugar inicial, pero con la particularidad que sea el más barato. ¡Eso es todo!

Naturalmente, la tentación es preguntarse: ¿tanto lío por esto? Bastaría con enumerar las ciudades, escribir los precios de cada tramo y después suma el costo de todos los segmentos. Se fija en todos los resultados, elige el que ofrezca el número más chico o el menor, ¡y listo! Todo cierto, pero hay un asterisco para considerar. Si uno tiene dos o tres ciudades, o pocas ciudades, el problema es de obvia solución como escribí recién. Pero, ¿qué pasaría si fueran ahora nada más que diez ciudades para conectar? En este caso, el número de rutas posibles se incrementa muy fuertemente. Ahora hay 3.628.800 sumas por analizar. Bueno, pensará usted, una computadora puede hacer eso rápido, ¿no es así? Sí, es verdad también. Pero aún a las computadoras más rápidas del mundo se les haría complicado resolver el caso siguiente: supongamos que usted elige las capitales de las 23 provincias argentinas. En ese caso, las formas de recorrerlas pasando una sola vez por cada una y volviendo al punto inicial da un número muchísimo más grande:

23.852.016.738.885.000.000.000,

Sí, con 23 ciudades hay más de ¡23 mil trillones de posibilidades! Creo que ahora el problema se hace más evidente. Y esto es sólo para 23 ¿Se imagina si hubiera 100?

Usted se debe/debería estar preguntando: y ¿en qué otros casos prácticos uno podría aplicar la solución a este problema? Antes de contestar la pregunta, quiero escribir que la ciencia no funciona de esa manera. El problema existe, y el sólo afán de resolverlo es motivo suficiente. No es una cuestión de cómo o dónde se usa. Se usa para satisfacer la curiosidad del ser humano … ¡nada menos! Pero, igualmente, en este caso puedo aportar algunas ideas aunque ninguna de ellas sea de mi especialidad. Por ejemplo, si usted estuviera a cargo de una planta en donde se construyen automóviles y tuviera que programar un robot para que elija la ruta más económica (sea en tiempo o energía consumida) que permita soldar determinados puntos pre-establecidos, ya con 23 de estos puntos, el programa que lleva el robot tendría que evaluar más de 23 mil trillones de casos. Lo mismo si uno tuviera un micro-chip de una computadora, o estuviera intentado secuenciar el ADN de algún organismo.

En el intento de resolver este problema, como sucede tantas veces en el ámbito científico se han disparado muchísimo otras tangentes que divergen del objetivo inicial pero que en sí mismas representan la posibilidad de descubrir algo que uno no imaginaba o contestar alguna pregunta que ni siquiera sabía que uno tenía. De hecho, el camino que los científicos especialistas en computación han ido recorriendo para resolver el Problema del Viajante de Comercio, ayudó a iluminar el poder de técnicas como la programación lineal. Uno de los líderes en el mundo en dedicarle su vida a tratar de encontrar la solución, Christos Papadimitriou (¿hace falta que diga que es un matemático de origen griego), lo describió no como un problema, sino como una adicción.

La mayoría de los expertos en el tema sostiene que es muy poco probable que alguna vez alguien encuentre una solución general para el problema que pueda usarse para cualquier combinación y número de ciudades, pero se van produciendo mejoras infinitesimales o muy minúsculas, en el sentido de que se diseñan algoritmos que permiten reducir el tiempo o el costo que ofrecen los que ya existen. Son avances incrementales, pequeños, pero todo suma. Uno de los algoritmos que patentó Nicos Christofides, encuentra soluciones aproximadas que a lo sumo son 50 por ciento más largas de las que imaginariamente llevaría la ruta ideal que uno busca. Pero hacer relativamente poco, en un trabajo publicado en julio del 2020 y actualizado en mayo del 2021, Anna Karlin, Nathan Kelin y Shayan Gharan de la Universidad de Washington State, especialistas en computación y matemáticos que trabajan en el oeste de Estados Unidos, publicaron un trabajo que mejora todo lo conocido en el intento de encontrar soluciones aproximadas.[2]

Una observación más. Hay una ONG muy famosa (en el mundo de la matemática): El Instituto Clay de Matemática (Clay Mathematics Institute). El Instituto se dedica a la difusión de la matemática. Cuando se fundó tenía su base en New Hampshire, en EEUU. Ahora, las actividades están conducidas desde Oxford, en Inglaterra. Pero menciono esta institución porque en mayo del año 2000, eligió una lista de siete problemas no resueltos (o abiertos) del mundo de la matemática. Uno de ellos es justamente, El Problema del Viajante de Comercio. Quien logre resolver alguno de ellos, cobrará un millón de dólares.

Un matemático ruso, Grigori Perelman, se hizo famoso porque fue quien demostró uno de los problemas: “La Conjetura de Poincaré”. Sin embargo, un grupo de matemáticos chinos intervino para decir que ellos también habían hecho contribuciones sustanciales sin las cuales Perelman no hubiera podido resolver la conjetura. Perelman se enojó tanto porque pusieran en duda su honestidad, y se negó a recoger el millón de dólares y volvió a St Petersburgo en donde hoy vive con su madre en condiciones muy precarias.

Por un instante, permítame escribir que deploro describir el caso de Perelman que es muy conocido en el mundo -matemático/académico- pero posiblemente sea un total desconocido para la mayoría. Lo deploro porque sirve para agregar más leña al fuego y fomentar aún más el estereotipo o la percepción que la sociedad tiene sobre los científicos en general, pero muy en particular por los matemáticos, pero es la verdad de lo que sucedió.

¿Por qué destacar esto hoy y ahora? Puede que este problema particular no tenga solución, al menos con las herramientas computacionales que tenemos hoy a nuestro alcance. Pero la historia está plagada de ejemplos de alguien que se acerca en forma cándida, que no se siente intimidada por la magnitud de lo que enfrenta, mira el problema desde otro ángulo, y logre resolver lo que parecía imposible. Abundan los ejemplos. Ojalá que alguien lo logre en el corto plazo y mientras tanto, poner en evidencia lo fascinante que resulta ser una suerte de detective dentro del mundo de la ciencia, tratando de descubrir lo que no descubrió nadie o ver algo en el lugar que estuvieron mirando miles de pares antes y no lograron ver nada. Ese desafío constante, esa llama de la curiosidad siempre viva y espíritu crítico que nos convoca, es lo que permite que el mundo avance. Por eso el orgullo de ser uno más de los subproductos de la educación pública, gratuita, laica y obligatoria de mi país.

 

[1] https://www.pagina12.com.ar/diario/contratapa/13-67031-2006-05-18.html

 

[2] https://arxiv.org/abs/2007.01409

  • El Oso Producciones El Oso Producciones
  • C&M Publicidad C&M Publicidad