POR ADRIáN PAENZA
Jueves, 04 Marzo de 2021
PROBLEMAS IRRESUELTOS: EL PROBLEMA DEL VIAJANTE DE COMERCIO
¿Cómo saber cuál sería el trayecto más barato?
PROBLEMAS IRRESUELTOS: EL PROBLEMA DEL VIAJANTE DE COMERCIO Por Adrián Paenza

Como se puede imaginar, si yo tuviera (o pretendiera) escribir una lista de todos los problemas irresueltos en matemática, me podría pasar la vida (no solo la mía sino también la suya y la de todo el resto de la humanidad) y no terminaría. Es que mientras yo escribo y usted lee, hay científicos que van contestando preguntas, pero por cada respuesta, por cada problema que parece ‘cerrarse’, se abren múltiples más de los que –quizás— no teníamos idea.

 

Por supuesto, no se me escapa que no todos los problemas tienen las mismas relevancia ni importancia. De hecho, hay problemas que llevan muchísimos años desde que fueron planteados, y tienen el atractivo ‘extra’, de que mucha gente muy famosa (dentro de la matemática), matemáticos relevantes que han intentado y no pudieron contestar la pregunta. Pero, por otro lado, no interprete que estoy diciéndole a usted, sí, a usted, que no lo intente, porque lo más posible es que algunos de estos problemas sean abordados y/o resueltos por personas que tengan la ‘temeridad’ de atacarlos con ingenuidad y de esa forma, en lugar de encontrarse con los caminos ‘sin salida’ que encontraron otros, terminarán haciendo algún aporte totalmente diferente, que no se le había ocurrido a nadie, y esa misma ingenuidad (si es que puedo seguir usando esa palabra) será determinante para encontrar la respuesta.

 

Una breve digresión. En Estados Unidos, en un lugar virtualmente perdido en el mapa, ‘allá arriba’ en el noreste, en una ciudad pequeña (Peterborough), en New Hampshire, un Estado muy pequeño (en población y superficie), allí se encuentra ubicada una institución sin fines de lucro pero que ha tomado una trascendencia mundial por razones que paso a explicar. Justamente en Peterborough está ubicado el Clay Mathematical Institute [1] (el Instituto de Matemática Clay). A comienzos de este siglo (XXI), el instituto planteó una lista con siete problemas, que es conocida con el nombre de “Los Problemas del Milenio” (“Millenium Problems”).

 

La institución —fundada hace casi 23 años (en 1998)— se compromete a entregar un millón de dólares a cualquier persona que pueda resolver alguno de los problemas. Así nomás. De todas formas, me quiero apurar a escribir lo siguiente: si bien resulta obvia la implicancia económica del premio, más allá de eso, el prestigio que le traería al autor, lo ubicaría –casi instantáneamente— en el panteón de los matemáticos más sobresalientes de la historia. Por lo tanto, si bien la compensación monetaria es obviamente no menor, desde el punto de vista del respeto que ganaría en la historia de esta ciencia es ciertamente inigualable.

 

Un aspecto interesante es que salvo uno de los problemas, son todos muy difíciles de enunciar (y por lo tanto comprender) para una persona que sea no matemática. Más aún: estoy convencido de que aún matemáticos profesionales, cuyas especialidades no son compatibles con cada problema, tendrían dificultades en comprender siquiera ‘cuál es el problema’ o ‘qué es lo que hay que demostrar y/o resolver’.

 

En anteriores entregas de esta misma columna ya les hable de otros problemas irresueltos, que nos resultan más accesibles, tales como el Problema de Collatz que también se conoce el Algoritmo de Siracusa (ver nota del 8/02/2020) o La Conjetura de Goldbach (nota del 1/08/2020).  Le cuento, el hecho de que sean más accesibles para comprenderlos o entender qué es lo que hay que resolver, no los hace menos difíciles (ni más fáciles). Mi idea es compartir con usted un poco de lo que sucede en un mundo que quizás le queda más alejado de su vida cotidiana. Creo que vale la pena leer e informarse sobre lo que pasa “dentro de la matemática”.

 

Una última cosa: aunque quizás usted (y ciertamente yo) no somos médicos, todos sabemos las dificultades que hay para encontrar soluciones a cierto tipo de cánceres, o con enfermedades autoinmunes, o con el Alzheimer o Parkinson, etc, etc… Y sin ir muy lejos, fíjese lo que sucedió con la pandemia que estamos viviendo.

 

De todas formas, nos es más fácil relacionarnos con ese tipo de problemas ‘irresueltos’ que con los que hay en la matemática. Mi objetivo acá entonces es poner en relieve lo que sucede con otra ciencia y que a la mayoría de la población o de las sociedades en todo el mundo les resulta totalmente transparente.

 

Ahora sí, después de esta introducción voy a escribir sobre el único que figura en la lista de los “Problemas del Milenio” del que escribí un poco más arriba. Es uno de esos problemas que si usted (o alguien) fuera capaz de resolver, podría agregar un millón de dólares a su cuenta bancaria. Eso es la que está dispuesto a pagar el Clay Mathematics Institute.

 

El problema es de enunciado realmente muy sencillo y se entiende sin dificultades. Claro, eso no quiere decir que sea fácil de resolver, ni mucho menos.

 

De hecho, usted verá que si sigue leyendo pondrá en duda varias veces que a alguien le puedan pagar semejante suma por resolver lo que parece ser una verdadera pavada. Sin embargo, hace más de 50 años que está planteado como tal (aunque si uno rastrea la historia llega hasta el principio del siglo XIX, en 1800) y, hasta ahora, nadie le encontró la vuelta. Acompáñeme por acá.

 

Una persona tiene que recorrer un cierto número de ciudades que están interconectadas (pueden ser conectadas a través de rutas por donde circulan automóviles, o vías de ferrocarril o también rutas aéreas). Es decir, siempre se puede ir de una hacia otra en cualquier dirección.

 

Además, otro dato importante es que uno sabe el costo de ir de una hacia otra (y viceversa). 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: elegir una ciudad en la que empezar el recorrido. Construir un itinerario que pase por cada una (y todas) de las ciudades una sola vez, y que termine en el mismo lugar inicial. Naturalmente, si el problema terminara allí, no sería un ‘problema’. Lo que falta es saber cuál, de todos los posibles caminos que se puedan diseñar, es….¡el más barato!

 

Eso es todo. No me diga que no le dan ganas de volver para atrás y leer de nuevo, porque estoy seguro que a esta altura, usted debe dudar de que entendió correctamente el enunciado del problema. En vista de la experiencia que tengo (y tuve) con todos aquellos a quienes les conté el problema por primera vez, puedo ‘casi’ asegurar que esto es lo que le está pasando a usted:

 

O usted cree que no entendió bien el planteo o, hay algo que anda mal en este mundo.

Sin embargo está todo bien, sólo que la dificultad aparece escondida. Los intentos que distintas generaciones de matemáticos han hecho tratando de resolverlo han permitido múltiples avances, sobre todo en el área de optimización, pero hasta ahora, el problema general no tiene solución [2].

 

Yo sé que en este momento usted duda de mí, duda de usted… duda de todo. Tiene que haber algo que esté mal. Sigamos.

 

Hagamos algunos ejemplos sencillos, con pocas ciudades.

 

Las voy llamar con letras. Para dos ciudades (A y B), dos caminos posibles. Empezar en A, ir a B y volver a A, o empezar en B, pasar por A y volver a B.

 

ABA y BAB.

 

Lo que hay que hacer después es estudiar los precios de cada tramo, sumarlos y por lo tanto, cada una de las dos posibles rutas implicará un costo. Uno compara, elige la más barata (aunque podrían ser las dos iguales), y se queda con esa. Listo.

 

Ahora hagamos lo mismo pero con tres ciudades (A, B y C). Si usted se fija, verá que hay seis caminos y como antes cuando había dos, escribo ‘en orden’ las seis formas posibles de recorrerlas:

 

ABCA BACB CABC ACBA BCAB CBAC.

 

Una vez más, uno les agrega los precios de cada segmento, los suma y obtiene el resultado final de cada itinerario. Después elige el más barato, y se terminó.

 

Para cuatro ciudades (A, B, C y D) hay veinticuatro caminos posibles (que detallo acá abajo):

 

ABCDA BCDAB CABDC DABCD

 

ABDCA BCADB CADBC DACBD

 

ACBDA BDACB CBADC DBACD

 

ACDBA BDCAB CBDAC DBCAD

 

ADBCA BACDB CDABC DCABD

 

ADCBA BADCB CDBAC DCBAD

 

Supongamos ahora que en lugar de cuatro ciudades, hubiera cinco.

 

¿Cuántos caminos posibles habrá? (Y acá estará la clave.) Quiero convencerla/o de que de las 24 posibles que había con cuatro ciudades, ahora, para cinco, el número aumenta mucho: hay 120. Vea por qué.

 

¿En cuántas ciudades se puede empezar el recorrido? Respuesta: en cualquiera de las cinco (A, B, C, D y E).

 

Una vez elegida la primera, ¿cuántas posibilidades quedan para la segunda ciudad? Respuesta: cualquiera de las cuatro restantes. O sea, nada más que para recorrer las primeras dos ciudades hay ya veinte posibles maneras de empezar:

 

AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC y ED.

 

¿Y ahora? ¿Cuántas posibilidades hay para la tercera ciudad? Como ya elegimos dos, nos quedan tres para elegir. Luego, como ya teníamos veinte maneras de empezar, y cada una de éstas puede seguir de tres formas, con tres ciudades, entonces ahora tenemos 60 (sesenta) formas de empezar con tres ciudades. (¿Advierte ya en dónde empieza a estar la dificultad?) Es como si estuviéramos construyendo un árbol, o las ramas de un árbol. Mientras tanto, yo sigo.

 

Para la cuarta ciudad a elegir, ¿cuántas posibilidades quedan?

 

Respuesta: dos (ya que son solamente dos las ciudades que no hemos utilizado en el itinerario que hicimos hasta ahora). Luego, para cada una de las 60 formas que teníamos de empezar con tres ciudades, podemos continuar con dos ciudades. Luego, tenemos 120 itinerarios con cuatro ciudades.

 

Y ahora, para el final, no nos queda nada para elegir, porque de las cinco ciudades que había, ya hemos seleccionado cuatro: la quinta queda elegida por descarte, es la única que queda.

 

Moraleja: tenemos 120 itinerarios.

 

Si usted relee lo que escribimos recién, al número 120 llegamos multiplicando los primeros cinco números naturales:

 

120 = 5 x 4 x 3 x 2 x 1

 

Este número se conoce con el nombre 5!, pero no es que se lea con gran admiración, sino que los matemáticos llamamos a este número el factorial de cinco. En el caso que estamos analizando, el número cinco es justamente el número de ciudades.

 

Es fácil imaginar lo que va a pasar si en lugar de tener cinco ciudades, se tienen seis (y le propongo que lo haga). El número de caminos posibles será:

 

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

 

Sigo algunos pasos más.

 

Siete ciudades, 7! = 5.040 posibles caminos

 

Ocho ciudades, 8! = 40.320 caminos

 

Nueve ciudades, 9! = 362.880 caminos

 

Diez ciudades, 10! = 3.628.800 caminos

 

Acá paro. Como usted se da cuenta, el total de rutas posibles que habría que analizar con sólo diez ciudades es de ¡más de tres millones seiscientos mil! Agregarle los precios de cada tramo, sumarlos y asociar a cada ruta con el número que saldría recorrer las ciudades en ese orden. Después, elegir la más barata.

 

La primera conclusión que uno saca es que el factorial de un número aumenta muy rápidamente [3] a medida que uno va avanzando en el mundo de los números naturales. Tan rápido aumenta, que lo invito a que usted haga las cuentas para convencerse.

 

Imagine que ahora usted es un viajante de comercio y necesita decidir cómo hacer para recorrer –por ejemplo- las capitales de las 23 provincias argentinas, de manera tal que el costo sea el menor posible. O sea, de acuerdo con lo que vimos recién, habría que analizar el factorial de 23 posibles caminos. Pero el factorial de 23 (que se escribe 23!) supera los 25.000 trillones de caminos posibles. Aún a las computadoras más potentes les resulta complicado decidir cuál de todos los recorridos es el óptimo.

 

23! = 25,852,016,738,885,000,000,000

 

Con las computadoras más potentes y más rápidas que existen hoy, aún con un ejemplo tan pequeño (solamente 23 ciudades), el número de caminos posibles (y el precio de cada itinerario) se ha transformado en un número gigantesco.

 

Como usted habrá advertido ya, la dificultad no está en escribir los caminos posibles, ni siquiera en estimar el costo. No. El problema reside en el número descomunal de posibilidades que hay que recorrer hasta poder elegir esa ruta óptima, y si con 23 ciudades hay más de 25.000 trillones, no hace falta que le diga lo que sucedería si uno tiene 100 o 1.000 ciudades.

 

Por lo tanto, la dificultad reside no en hacer las cuentas, ni siquiera en el método a emplear, ni en sumar los costos y después comparar. El problema, insalvable por ahora, es que hay que hacerlo con una cantidad descomunal de rutas, que como escribí más arriba, aún en los casos más sencillos, parece inabordable.

 

Hay varios casos particulares que fueron resueltos, pero en esencia el problema está abierto.

 

Un último comentario: con los actuales modelos de computación, el problema no parece que tenga solución. Hará falta entonces que aparezca alguna nueva idea que revolucione todo lo conocido hasta acá.

 

Acá termino con este brevísimo recorrido. ¿Habré logrado interesarla/o? ¿Habré logrado motivarla/o? ¿Sabe por qué le pregunto? Es muy claro que usted no va a cambiar su vida leyendo y/o tratando de interpretar los problemas que figuran más arriba, pero, si uno tenía ni idea de lo que pasa en este «mundo» (el de la matemática), ¿no siente que se ha mejorado un poco como persona sabiendo que en el mundo hay muchísima gente pensando soluciones a problemas que nosotros no teníamos la menor idea que existían?

 

En todo caso, permítame decirle que a mí sí, tanto como me interesaría saber (si pudiera), en qué están pensando los científicos en el mundo, todos los días, no importa la disciplina, no importa el lugar, no importan las condiciones, no importa nada: cuando se despiertan a la mañana y van a ‘trabajar’, ¿se imagina algo mejor que tener un problema irresuelto y pensar que ese día, ese día particular puede que se le ocurra algo que mejore la dirección a la que le estaba apuntando o que le dé una idea que no tenía antes? ¿Qué cosa mejor le podría o puede pasar a uno en la vida (profesional, claro está), que contribuir en ese sentido?

 

Aunque no esté de acuerdo con lo que escribí (no estoy seguro de que yo lo esté), creo que vale la pena pensar el último párrafo.

 

  [1] http://www.claymath.org/  Esta es la página official del Clay Mathematical Institute y los problemas los puede encontrar acá: http://www.claymath.org/millennium-problems

 [2] En realidad, está ‘mal’ que yo diga que no tiene solución. Solución tiene, y es muy sencilla: alcanza con listar todos los caminos posibles y quedarse con el más corto. El problema reside en cuánto tiempo necesita uno para poder descubrir este camino particular. Las formas conocidas hasta hoy (aún en casos sencillos, con un ‘pequeño’ número de ciudades) llevarían siglos. Hablando en términos un poco más ‘técnicos’, el objetivo es encontrar un algoritmo polinomial. Los que tenemos hasta aquí tienen una complejidad exponencial.

[3] Por supuesto, cuando escribo que ‘el factorial de un número aumenta muy rápidamente’, la rapidez termina siendo subjetiva. La pregunta sería: “¿más rápidamente comparado con qué?” Y tendría razón en cuestionarme la frase. Pero para no extenderme mucho, apelo a su generosidad para entender lo que quiero decir. En todo caso, le propongo que usted haga se ocupe de comparar el crecimiento del factorial de un número con otro tipo de multiplicaciones o incluso, en situaciones de crecimiento exponencial.



COMPARTIR