3

¡Deja que la paloma conduzca el autobús!

Por un lado, el conductor de autobús podría estar preocupado por que la paloma no fuese capaz de conducir el vehículo de forma segura. Por el otro, tal vez le preocupase más que la paloma no pudiese hacer una ruta para recoger de manera eficaz a todos los pasajeros en las diversas paradas a través de la ciudad.

BRETT GIBSON, MATTHEW WILKINSON y DEBBIE KELLY,
Animal Cognition

Mo Willems hace dibujos desde que tenía tres años. Le preocupaba que los adultos no fuesen sinceros en sus alabanzas, así que empezó a escribir historias graciosas. Pensaba que las risas forzadas serían más fáciles de detectar. En 1993, se unió al equipo de guionistas y animadores del emblemático programa Barrio Sésamo, con el que ganó seis premios Emmy en diez años. Su serie infantil de dibujos para televisión, Oveja en la ciudad, estaba protagonizada por Sheep, cuya idílica vida rural se ve arruinada cuando la organización militar secreta del General Concreto lo quiere para su pistola de rayos alimentada por energía ovina. Su primera incursión en la literatura infantil mantuvo el tema animal con ¡No dejes que la paloma conduzca el autobús!, que le valió una medalla Carnegie por su adaptación animada y una mención de honor Caldecott, que reciben los seleccionados para la Medalla Caldecott. La protagonista es una paloma (obvio) que recurre a todos los trucos en el manual para convencer al lector de que se le debería dejar conducir un autobús cuando el conductor humano de siempre tiene que irse de repente.

El libro de Willems tuvo una secuela científica inesperada en 2012, cuando la muy respetable revista Animal Cognition publicó un muy respetable artículo de los muy respetables investigadores Brett Gibson, Matthew Wilkinson y Debbie Kelly. En él demostraban de manera experimental que las palomas pueden encontrar soluciones casi óptimas a casos sencillos de una conocida curiosidad matemática: el problema del viajante. El título de su artículo fue «¡Deja que la paloma conduzca el autobús! Las palomas pueden planificar rutas futuras en una habitación».1

Que no se diga que los científicos no tienen sentido del humor. Ni que los títulos llamativos no ayudan a hacerse notar.

El problema del viajante no es solo una curiosidad. Es un ejemplo muy importante de un tipo de cuestiones con una relevancia práctica enorme denominado optimización combinatoria. Los matemáticos tenemos la costumbre de plantear interrogantes profundos y relevantes en términos en apariencia triviales. Unos congresistas de Estados Unidos han denunciado el derroche de fondos públicos en la teoría de nudos, ignorantes de que esta es un área fundamental de la topología de dimensiones bajas, con aplicaciones en el estudio del ADN y en teoría cuántica. Las técnicas básicas en topología incluyen el teorema de la bola peluda y el teorema del sándwich de jamón, así que supongo que nos lo hemos buscado. Pero no se trata solo de nosotros. No me preocupa el desconocimiento, es algo que le puede ocurrir a cualquiera, pero ¿por qué no preguntan?2

Sea como sea, el caso de trivialidad significativa al que se refiere este capítulo se origina en un libro útil para (quién lo iba a decir) viajantes de comercio. Vendedores puerta a puerta. Aún los recuerdo, aunque muchos no lo hagan. A menudo vendían aspiradoras. El viajante de comercio alemán de 1832, como cualquier hombre de negocios razonable (y en esa época siempre era un hombre), daba mucha importancia a emplear su tiempo con eficacia y a reducir costes. Por suerte, la solución estaba al alcance de la mano en la forma del manual Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu sein – von einem alten Commis-Voyageur (El agente comercial itinerante: cómo debe ser y qué tiene que hacer para conseguir pedidos y garantizar el feliz éxito de su negocio. Por un viajante de comercio veterano.) Este anciano vendedor peripatético señalaba que:

Elnálcio lleva al agente comercial itinerante ahora aquí, luego allí, y es imposible señalar de manera conveniente rutas de viaje que sean adecuadas para todos los casos que se presentan. Sin embargo, a veces, mediante una elección y una preparación cuidadosas del viaje puede ahorrarse tanto tiempo que no creo que podamos evitar dar algunas reglas sobre esto también... El aspecto más importante consiste siempre en visitar cuantos sitios sea posible sin tener que pasar dos veces por el mismo lugar.

El manual no proponía cálculo alguno para resolver este problema, pero daba ejemplos de cinco recorridos que se suponían óptimos alrededor de Alemania (uno pasaba a través de Suiza). La mayoría de ellos implicaban viajes secundarios en los que se pasaba por el mismo lugar dos veces, algo muy práctico para quien se aloja por la noche en una posada y pasa el día de visita por la zona. Pero había uno que no hacía paradas repetidas. Una solución moderna al mismo problema demuestra que la respuesta del manual es bastante buena, como puede verse en la imagen.

Este dilema se vino a conocer como el problema del viajante, o TSP, por sus siglas en inglés, pero luego se cambió a problema de la persona viajante, para evitar un uso sexista del lenguaje (tiene las mismas siglas en inglés, lo que es muy práctico). Es un ejemplo fundacional de la rama de las matemáticas conocida como optimización combinatoria. Lo que quiere decir «encontrar la mejor opción entre un conjunto de posibilidades que es demasiado grande como para comprobarlas una a una». Es curioso que el nombre TSP no parece haberse empleado de manera explícita en ninguna publicación referente a este problema antes de 1984, aunque su uso fuese habitual mucho antes en discusiones informales entre matemáticos.

Recorrido (1.285 km) por 45 ciudades alemanas tomado del manual de 1832, representado por las rectas continuas (en negrita y delgadas). Las líneas continuas en negrita gruesa y discontinuas representan el recorrido más corto (1.248 km) encontrado con métodos modernos.

Para ser una cuestión con un origen tan pragmático como este, el TSP ha llevado a la comunidad matemática a profundidades muy hondas, incluido el problema del milenio «¿P ≠ NP?», cuyo premio de un millón de dólares sigue a la espera de un ganador. Este dilema se pregunta, en un sentido técnico preciso, si dado un interrogante para el que puede verificarse de manera eficaz una respuesta propuesta (una estimación aproximada, si se quiere), es posible encontrar siempre la solución con eficacia. La mayor parte de los matemáticos y de los informáticos teóricos creen que la respuesta es que no. Sin duda, comprobar cualquier estimación concreta puede hacerse con mucha más rapidez que dar con la solución correcta. Después de todo, si alguien muestra un rompecabezas de 500 piezas resuelto, lo más habitual es que un simple vistazo permita saber si lo ha hecho bien. En cambio, resolverlo desde el principio es harina de otro costal. Por desgracia, los rompecabezas no proporcionan una respuesta. Constituyen una metáfora útil, pero no tienen validez desde el punto de vista técnico. De modo que ahora mismo nadie puede demostrar que la creencia de que P es diferente de NP es verdadera, ni lo contrario. Ese es el motivo por el que lograrlo se paga con un estupendo millón de dólares.3 Volveré sobre P ≠ NP más adelante, pero veamos antes los primeros avances en la resolución del TSP.

 

*

 

La época de los viajantes de comercio pasó hace mucho y la de las personas viajantes de comercio, menos machistas, le pisó los talones. En la era de internet, es muy raro que las empresas manden a alguien de ciudad en ciudad con una maleta llena de muestras para vender sus productos. Como es habitual (eficacia irrazonable), este cambio cultural no ha hecho que el TSP quede obsoleto. Con el crecimiento exponencial de las compras online, la necesidad de maneras eficaces de determinar rutas y horarios ha cobrado incluso más importancia para todo, desde paquetes o pedidos del supermercado hasta pizzas. Tal vez deberíamos cambiar el nombre del TSP a «problema de la compra del súper»: ¿cuál es el recorrido óptimo para la furgoneta de reparto?

La portabilidad de las matemáticas también entra en juego. Las aplicaciones del TSP no se limitan a recorridos entre ciudades o a lo largo de las calles de la ciudad. En la pared de nuestro salón cuelga un gran cuadrado de tela negra bordado en azul con un elegante patrón de espirales ribeteadas de lentejuelas basado en la conocida serie de Fibonacci. El diseñador lo ha llamado las «lentejuelas de Fibonacci».4 Lo hizo empleando una máquina controlada por ordenador capaz de bordar cualquier diseño hasta el tamaño de un edredón. La aguja que cose los hilos está unida a una varilla y puede desplazarse a lo largo de esta. A su vez, la varilla es capaz de moverse en perpendicular a su longitud. Es posible llevar la aguja a donde se quiera mediante la combinación de ambos movimientos. Por razones prácticas (aprovechamiento del tiempo, desgaste de la máquina o ruido) no es deseable que la aguja salte de un lado a otro por todas partes, por lo que la distancia total de desplazamiento debe reducirse al mínimo. Es un problema muy parecido al TSP. El linaje de estas máquinas se remonta a los albores del diseño gráfico por ordenador y a un dispositivo conocido como plotter XY, que movía un rotulador de la misma manera.

Dilemas como este abundan en ciencia. Érase una vez que los astrónomos más destacados poseían sus propios telescopios o los compartían con unos pocos colegas. Podía variarse la dirección de los instrumentos con facilidad para apuntar a nuevos cuerpos celestes, así que improvisar era sencillo. Ya no es así, porque los telescopios que emplean los astrónomos son enormes, tienen un coste desorbitado y funcionan por internet. Se tarda mucho en dirigirlos hacia objetos nuevos y los instrumentos no pueden emplearse para hacer observaciones mientras se desplazan. Si los objetivos se recorren en el orden equivocado, se pierde mucho tiempo al mover el telescopio una gran distancia y luego volver casi al punto de partida. Al secuenciar ADN, las secuencias fragmentarias de las bases del ácido tienen que unirse de manera correcta entre sí y debe optimizarse el orden en el que se hace esto para evitar desperdiciar el tiempo de cálculo del ordenador.

Otras aplicaciones van desde trazar rutas para aeronaves de manera eficaz hasta el diseño y la fabricación de microchips y placas de circuitos impresos en informática. Se han empleado soluciones aproximadas del TSP para encontrar recorridos eficaces para el servicio de comidas a domicilio para personas dependientes y para optimizar el reparto de sangre en hospitales. Incluso una versión del TSP apareció en la «guerra de las galaxias», mejor llamada la hipotética Iniciativa de Defensa Estratégica del presidente Reagan, según la cual un potente láser que orbitase la Tierra se habría dirigido contra una serie de misiles nucleares atacantes.

 

*

 

Karl Menger, algunas de cuyas aportaciones se consideran ahora como precursoras de los fractales, parece haber sido el primer matemático que escribió sobre el TSP, en 1930. Llegó hasta el problema desde una perspectiva muy diferente. Había estado estudiando las longitudes de curvas desde el punto de vista de las matemáticas puras. En esa época, ese parámetro se definía como el valor más grande obtenido al sumar las longitudes de cualquier aproximación poligonal a la curva cuyos vértices fuesen un conjunto finito de puntos en la curva, recorridos en el mismo orden en el que se sitúan sobre ella. Menger demostró que se obtiene el mismo resultado si se sustituye cada polígono por un conjunto finito de puntos sobre la curva y se calcula la distancia total mínima a lo largo de cualquier polígono con esos vértices en cualquier orden que se desee. La relación con el problema del viajante estriba en que el trayecto más corto de Menger es el que resuelve el TSP si se consideran los vértices del polígono como ciudades. Lo denominó «problema del mensajero», porque decía que era válido tanto para carteros como para agentes comerciales itinerantes y escribió:

Este problema puede resolverse mediante un número finito de intentos. No se conocen reglas que reduzcan el número de intentos por debajo de la cantidad de permutaciones de los puntos dados. La norma según la cual se debe ir desde el punto inicial al más cercano, luego al más próximo a este, etcétera, no conduce en general a la ruta más corta.

Esta cita demuestra que comprendía dos características principales del problema. La primera, es que existe un algoritmo para encontrar la respuesta. Solo hay que comprobar todos los recorridos uno tras otro, calcular sus longitudes y ver cuál es el más corto. El número total de trayectos posibles es precisamente la cantidad de permutaciones de los puntos, que es finita. En la época en que escribía, no se conocía otro algoritmo mejor, pero no es factible comprobar todas las posibilidades para más de una docena de ciudades o así porque hay demasiados recorridos. En segundo lugar, sabía que el método «evidente» (ir de un punto cualquiera al siguiente más cercano) no suele funcionar. Los expertos llaman a este método «heurística del vecino más cercano». El dibujo muestra un motivo por el que falla.

Menger fue profesor invitado en la Universidad de Harvard durante seis meses, entre 1930 y 1931, y el gran topólogo Hassler Whitney asistió a sus clases e hizo algunas sugerencias sobre la cuestión. Un año después, Whitney pronunció una conferencia en la que mencionó el descubrimiento del recorrido más corto entre los 48 estados que había entonces en Estados Unidos. El nombre «problema de los 48 estados» estuvo en circulación durante un tiempo y nadie parece saber con certeza quién acuñó la denominación más pegadiza de «problema del viajante». La primera referencia impresa conocida en la que se emplea el término TSP es un informe de Julia Robinson de1949.

Menger prosiguió su trabajo en el TSP y en problemas relacionados. En 1940, Laszlo Fejes Tóth investigó lo que viene a ser la misma cuestión: encontrar el camino más corto a través de n puntos en el cuadrado unidad. En 1951, Samuel Verblunsky demostró que la respuesta tiene una longitud menor que 2 + √2·8n. Varios matemáticos demostraron teoremas un poco mejores según los cuales la longitud mínima sobre n puntos en una región fija no es mayor que alguna constante multiplicada por la raíz cuadrada de n, para constantes que se hacían más pequeñas cada vez.

A finales de la década de 1940, una de las instituciones más destacadas en investigación operativa era la Corporación RAND de Santa Mónica, en California. Sus investigadores habían hecho mucho trabajo en una cuestión relacionada, el problema del transporte, y George Dantzig y Tjalling Koopmans sugirieron que sus aportaciones a lo que se conoce hoy en día como programación lineal podían ser relevantes al TSP. La programación lineal es un potente marco práctico para muchos problemas de optimización combinatoria. Constituye un método para maximizar alguna combinación lineal de variables, sometida a desigualdades que afirman que ciertas combinaciones lineales más deben ser positivas o negativas. Dantzig inventó el primer algoritmo práctico, el método símplex, que todavía se emplea mucho hoy en día. Las desigualdades definen un poliedro convexo multidimensional y el algoritmo mueve un punto a lo largo de las aristas que aumentan la cantidad que queremos maximizar hasta que se queda atascado.

Una manera en la que falla la heurística del vecino más cercano. En el recorrido de la izquierda, se parte de A y se va siempre a la ciudad más cercana de aquellas que todavía no se han visitado, por lo que se pasa por ABCDE en orden. No obstante, el recorrido de la derecha, que visita ACBDE, es más corto.

Los investigadores de RAND Dantzig, Delbert Fulkerson y Selmer Johnson hicieron el primer progreso significativo de verdad en el TSP mediante el empleo del método de programación lineal de Dantzig. Lo adaptaron para aplicarlo a este problema e introdujeron nuevos métodos sistemáticos, en concreto, el uso de «planos de corte». La conclusión fue un límite inferior para la longitud óptima del recorrido. Si puede encontrarse un trayecto cuya longitud sea tan solo un poco mayor que la ideal es que se anda cerca de la respuesta, en cuyo caso la astucia instintiva puede en ocasiones rematar la tarea. Dantzig, Fulkerson y Johnson emplearon estas ideas para obtener la primera solución del TSP con un número razonable de poblaciones, en concreto, el recorrido más corto por 49 ciudades (una en cada uno de los 48 estados de Estados Unidos más Washington D. C.). Es probable que este fuese el problema que Whitney mencionó en la década de 1930 y es la versión exacta a la que hizo referencia Robinson en 1949.

 

*

 

En 1956, el pionero de la investigación de operaciones Merrill Flood argumentó que es presumible que el TSP sea complejo. Esto plantea una duda fundamental: ¿hasta qué punto? Para responderla, debemos volver a considerar P y NP, esas medidas de complejidad computacional que valen un millón de dólares. Parece muy probable que Flood tuviera razón.

Los matemáticos siempre han prestado atención a que los métodos para resolver problemas sean eficientes, aunque, si no hay más remedio, son de la opinión de que cualquier método es mejor que ninguno. Para propósitos estrictamente teóricos, el mero hecho de ser capaces de demostrar que existe una solución a un interrogante puede ser un adelanto enorme. ¿Por qué? Porque si no es posible tener la certeza de que haya una, buscarla podría ser una pérdida de tiempo.

Mi ejemplo favorito en este sentido es el que yo llamo «la tienda de Madre Gnat». Bebé Gnat flota sobre el suelo a 30 centímetros (metros, millas... cualquier cosa mayor que cero) de altura. Madre Gnat quiere hacer una tienda que tenga su base en el suelo y que cubra a Bebé Gnat y quiere emplear la menor cantidad de tela posible. ¿Qué tienda tiene el área más pequeña? Si representamos a Bebé Gnat por un único punto, la respuesta es que no existe tal cosa. Se puede hacer una que sea cónica, alta y delgada con cualquier superficie mayor que cero, pero si tiene un área superficial nula es una línea, no una tienda. Dada cualquiera de ellas, hay otra que cumple los requisitos empleando la mitad de tela. Así que no puede haber un área que sea la más pequeña.

Respecto al TSP, existe sin duda alguna una solución para cualquier conjunto finito de ciudades dispuestas como se quiera, porque el número de recorridos posibles es limitado. Esto garantiza que no se pierde el tiempo cuando se busca el trayecto más corto, pero no dice cuál es este. Si se busca desenterrar un tesoro escondido, no sirve de nada saber que está sin duda en alguna parte porque no es factible excavar todo el planeta.

El científico de la computación Donald Knuth señaló, hace mucho, que en informática hace falta algo más que una prueba de que existe una respuesta. Se necesita saber cuánto va a costar encontrarla. No en euros y céntimos, sino en esfuerzo de cálculo. La rama de las matemáticas que aborda este problema se llama teoría de la complejidad computacional. En muy poco tiempo ha pasado de ser unas pocas ideas sencillas a un conjunto sofisticado de teoremas y métodos. Sin embargo, hay una distinción básica que refleja en cierta medida, en términos muy simples, la diferencia entre una solución eficiente y otra que no lo es.

La cuestión principal es esta: ¿a qué velocidad crece el tiempo de ejecución (medido como el número de pasos en el cálculo) en cualquier método para calcular la respuesta a un interrogante en comparación con el tamaño de los datos necesarios para formular el problema en primer lugar? En concreto, si hacen falta n dígitos binarios para plantearlo, ¿cómo depende el tiempo de ejecución de n? Para algoritmos eficientes, este parámetro tiende a crecer como una potencia de n, digamos n² o n³. Se dice que estos se ejecutan en tiempo polinómico y se simbolizan como clase P. Por el contrario, los que no son eficientes crecen mucho más rápido, a menudo en tiempo exponencial, como 2n o 10n. El algoritmo que prueba todos los recorridos en el TSP es de este tipo. ¡Se ejecuta en tiempo factorial n!, que crece a mayor velocidad que cualquier exponencial. Hay una zona gris entre medias en la que el tiempo de ejecución es superior a cualquier tiempo polinómico, pero inferior a uno exponencial. A veces estos algoritmos son eficientes, en otras ocasiones no. Para los propósitos de la presente consideración podemos adoptar un punto de vista muy estricto y arrojarlos a todos ellos a un cubo de basura marcado «no P».

Este no es equivalente a NP.

Estas siglas inducen a confusión porque representan una idea más sutil todavía: tiempo polinómico no determinista. Esta se refiere al tiempo de ejecución de un algoritmo que puede decidir si cualquier solución concreta propuesta es correcta. Recordemos que un número es primo si solo es divisible por 1 y por sí mismo. De modo que 2, 3, 5, 7, 11, 13 etcétera, son primos. El resto son compuestos. Es decir, 26 es compuesto porque es igual a 2 × 13 y los números 2 y 13 son los factores primos de 26. Supongamos que se quiere encontrar un factor primo de una cifra con doscientos dígitos decimales. Nos pasamos un año entero a la búsqueda de uno, sin encontrarlo, y en nuestra desesperación consultamos el oráculo de Delfos. Nos dice que la respuesta es cierto número muy grande. No tenemos ni idea de cómo ha llegado a este resultado (después de todo, es un oráculo con milagrosas dotes de adivinación), pero podemos sentarnos y echar cuentas para ver si el número que nos ha dicho divide de verdad la enorme cifra que hemos tomado en consideración. Un cálculo así es muchísimo más fácil que encontrar el factor primo en sí mismo.

Supongamos que cada vez que el oráculo ofrece una solución podemos comprobar si es correcta mediante el empleo de un algoritmo de tiempo polinómico (P). En ese caso, el problema en sí mismo es de clase NP (polinómico no determinista). La tarea del oráculo es mucho más difícil que la nuestra, pero siempre podemos decidir si nos ha dado la respuesta acertada.

Es razonable que comprobar una solución propuesta sea mucho más sencillo que encontrarla. Desde un primer momento, ver si el tesoro está enterrado en un punto marcado con una X es más fácil que descubrir dónde está la X. Para poner un ejemplo matemático, casi todo el mundo piensa que encontrar los factores primos de un número es mucho más difícil que comprobar si un primo dado es un factor. La prueba más evidente es que se conocen algoritmos que pueden verificar a gran velocidad cualquier factor propuesto, pero no dar con él. Si P = NP, entonces dado cualquier problema que tenga una solución rápida y comprobable, también sería posible encontrar la respuesta con rapidez. Esto suena demasiado bien como para ser cierto y la experiencia de los matemáticos a la hora de resolver problemas es la contraria. Así que casi todo el mundo cree que P ≠ NP.

No obstante, todos los intentos de demostrar esto, o lo contrario, han fracasado. Puede verificarse que un problema es NP escribiendo un algoritmo explícito y calculando su tiempo de ejecución, pero para comprobar que no está en P hay que tomar en consideración todos los algoritmos posibles para resolver el cálculo y demostrar que ninguno de ellos está en la clase P. ¿Cómo se hace esto? Nadie lo sabe.

Un hecho curioso que surge a partir de estos intentos es que una cantidad enorme de problemas candidatos están en la misma situación. Todos son NP. Es más, si puede demostrarse que uno cualquiera de ellos no pertenece a P, entonces ninguno pertenece a P. Uno para todos y todos para uno. Se dice que problemas como este son NP-completos. Una categoría relacionada y más amplia es NP-complejo. Esta consiste en algoritmos que pueden simular la solución de cualquier problema NP en tiempo polinómico. Si resulta que este algoritmo tiene un tiempo de ejecución polinómico, esto demuestra de manera automática que lo mismo es cierto para cualquier problema NP. En 1979, Michael Garey y David Johnson demostraron que el TSP es NP-complejo.5 Si se asume que P ≠ NP, esto implica que todo algoritmo que lo resuelve tiene un tiempo de ejecución mayor que cualquier polinomio.

Flood tenía razón.

 

*

 

Eso no es excusa para rendirse, porque hay al menos dos salidas posibles.

Una, que pasaré a explorar enseguida, se basa en la experiencia de problemas en la práctica. Si un problema es no P, entonces no es factible resolverlo en el peor de los casos. Pero a menudo, el peor de los casos resulta ser muy retorcido y no es característico de los ejemplos que se encuentran en el mundo real. Así que los matemáticos que trabajaban en investigación de operaciones se propusieron ver cuántas ciudades podían gestionar en situaciones reales. Y resultó que las variaciones en el método de programación lineal propuestas por Dantzig, Fulkerson y Johnson se desempeñaban a menudo extraordinariamente bien.

En 1980, el récord estaba en 318 ciudades. En 1987, ya eran 2.392 y para 1994, se había elevado el listón hasta las 7.397, un resultado que consumió cerca de tres años de tiempo de CPU en una red de ordenadores muy potentes. En 2001, se obtuvo una solución exacta para 15.112 ciudades alemanas mediante el empleo de una red de 110 procesadores. Se habrían necesitado más de veinte años en un ordenador normal de sobremesa. En 2004, se resolvió el TSP para la totalidad de las 24.978 poblaciones que hay en Suecia y en 2005, el Concorde TSP Solver halló la solución al problema para un recorrido de todos y cada uno de los 33.810 puntos que había sobre una placa de circuito impreso. Batir récords no es el único motivo para estas investigaciones. Los métodos empleados para ello funcionan de hecho con mucha rapidez para problemas más pequeños. Es habitual que se puedan resolver hasta cien ciudades en unos pocos minutos y llegar al millar en unas cuantas horas en un procesador normal de sobremesa.

La otra opción es conformarse con menos: una solución que no esté muy alejada de la óptima, pero que sea más fácil de encontrar. En algunos casos, esto puede lograrse mediante el empleo de un descubrimiento sorprendente hecho en 1890 en una rama de las matemáticas tan novedosa que muchas de las figuras destacadas en la época no pensaban que tuviese valor alguno y, a menudo, no creían en las respuestas que investigadores más visionarios encontraban poco a poco. Lo que es peor, los problemas que estos últimos abordaban parecían ser «matemáticas por sí mismas», sin relación perceptible con ninguna otra cosa en el mundo real. En general, se consideraba que sus resultados eran muy artificiosos y las nuevas formas geométricas que construían se calificaban de «patológicas». Muchos pensaban que, incluso si esas conclusiones eran correctas, no aportaban ni un ápice a favor de la causa de las matemáticas y que solo ponían obstáculos insensatos al progreso, en una orgía autocomplaciente de veleidades lógicas.

 

*

 

Un método para encontrar buenas soluciones, aunque no sean óptimas, al TSP surgió a partir de uno de estos obstáculos insensatos. Durante unas pocas décadas en torno a 1900, las matemáticas experimentaron una transición. Se había agotado el espíritu intrépido inicial de avances temerarios que pasaban por alto los detalles incómodos y su despreocupación por problemas básicos tales como «¿de qué estamos hablando en realidad aquí?» o «¿de verdad es esto tan evidente como pensamos?» había sembrado confusión y perplejidad donde debía haber claridad y comprensión. Las preocupaciones en torno a áreas avanzadas como el cálculo, en la que los matemáticos habían diseminado procesos infinitos a diestro y siniestro con alegre indolencia, empezaban poco a poco a desandar el camino desde los misterios para iniciados hasta los lugares comunes. En lugar de albergar dudas acerca de las integrales de funciones matemáticas complicadas, como los logaritmos complejos, muchos se preguntaban qué era una función. En vez de definir una curva continua como «aquella que puede dibujarse libremente con la mano», se buscaba un rigor mayor, que se echaba en falta. Incluso la naturaleza de algo tan básico y evidente como un número se demostraba esquiva. No solo en el caso de desarrollos novedosos, tales como los complejos, sino también para los archiconocidos números naturales 1, 2, 3. Las matemáticas convencionales habían proseguido su avance bajo la asunción táctica de que los problemas de este tipo acabarían por resolverse y de que todo se arreglaría. El estatus lógico de los cimientos podía dejarse sin peligro en manos de quisquillosos y pedantes. Y aun así... empezó a cristalizar un sentimiento generalizado de que este enfoque despreocupado de la disciplina no podía continuar mucho tiempo más.

Las cosas empezaron a torcerse de verdad cuando los audaces métodos anteriores empezaron a arrojar respuestas que se contradecían entre sí. Teoremas en cuya veracidad se confiaba desde hacía mucho resultaron ser falsos en circunstancias excepcionales, por lo general bastante extrañas. Una integral calculada de dos maneras diferentes daba dos resultados distintos. Una serie que se creía convergente para todos los valores de la variable divergía en ocasiones. No era tan catastrófico como descubrir que 2 + 2 a veces da 5, pero hizo que algunas personas se preguntasen qué eran en realidad 2 y 5, por no hablar de + e =.

De modo que, sin dejarse desanimar por una mayoría de agoreros (o al menos no tanto como para cambiar de opinión), unos pocos quisquillosos escarbaron túneles por todo el edificio de las matemáticas, desde las elevadas alturas hasta los sótanos, en busca de terreno firme sobre el que empezar a renovar por completo la construcción.

Como en todas las reformas, el resultado final fue diferente del punto de partida de una manera sutil pero inquietante. La noción de curva en el plano, que estaba presente desde la época de la Grecia antigua, reveló complejidades ocultas. Los ejemplos tradicionales (los círculos, las elipses y las parábolas de Euclides y Eratóstenes, la cuadratriz que los griegos empleaban para la trisección del ángulo y la cuadratura del círculo, la lemniscata en forma de ocho del neoplatónico Proclo, los óvalos de Giovanni Domenico Cassini, las cicloides y su progenie más compleja, tales como las hipocicloides y epicicloides de Ole Rømer) conservaban su propia fascinación y habían conducido a avances notables. Sin embargo, del mismo modo que los animales domesticados constituyen una imagen engañosa de la vida en las selvas tropicales y en las extensiones desérticas de la Tierra, estas curvas eran demasiado mansas como para ser representativas de las bestias salvajes que merodean por la jungla matemática. Como ejemplos de la complejidad potencial de las curvas continuas, eran demasiado sencillas y se comportaban demasiado bien.

Una de las características más fundamentales de las curvas, tan evidente que nadie se atrevía a ponerla en duda, es que son delgadas. Como escribió Euclides en sus Elementos, «una línea es una longitud sin anchura». El área de una línea (solo de esta, no de aquello que encierra) es, desde luego, cero. Sin embargo, en 1890, Giuseppe Peano describió una construcción de una curva continua que recubre por completo el interior de un cuadrado.6 No se limita a ir de un lado a otro dentro del área en un garabateo complicado que se acerca a cualquier punto, sino que atraviesa todos los puntos en la superficie de manera exacta. Desde luego, la curva de Peano «no tiene anchura», en el sentido de que se construye al trazar una línea con un lápiz cuyo extremo es un único punto geométrico, pero da vueltas de una manera muy enrevesada y pasa varias veces por las regiones que ya ha visitado antes. Peano se dio cuenta de que si se hace ondulada hasta lo infinito, de forma controlada y cuidadosa, acabará por recubrir toda la superficie. En particular, el área de la curva es la misma que la del cuadrado, de modo que no es cero.

Este descubrimiento supuso una conmoción de la intuición inocente. En esa época, las curvas de este tipo se calificaron de «patológicas» y muchos matemáticos reaccionaron ante ellas del modo en que habitualmente se hace ante lo enfermizo: con miedo y asco. Más adelante, el gremio se acostumbró a ellas y asumió las profundas lecciones topológicas que imparten. Hoy en día, la curva de Peano se entiende como un ejemplo temprano de geometría de fractales y se comprende que estos no son en modo alguno inusuales ni patológicos. Son lugares comunes, incluso en las matemáticas, y en el mundo real proporcionan modelos excelentes de estructuras naturales muy complejas, tales como nubes, montañas y costas.

Los pioneros de esta nueva era de las matemáticas escrutaron los conceptos intuitivos antiguos, como continuidad y dimensión, y empezaron a plantear preguntas de difícil respuesta. En lugar de asumir que podían salirse con la suya con las triquiñuelas tradicionales empleadas en ramas más sencillas de la disciplina, estos precursores se preguntaron si esos trucos funcionaban con una generalidad suficiente y, de ser así, por qué lo hacían. O, si no sucedía tal cosa, qué era lo que fallaba. Este enfoque escéptico molestó a muchos matemáticos convencionales, que lo percibieron como una actitud negativa sin razón de ser. En 1893, Charles Hermite escribió a su amigo Thomas Stieltjes: «Me aparto con terror y horror de este lamentable flagelo de funciones continuas sin derivaciones».

Los tradicionalistas estaban mucho más interesados en ampliar las fronteras y en asumir que todo en el jardín lógico era encantador. Sin embargo, el nuevo escepticismo, con su vendaval de desafíos estrafalarios a la intuición, era una reacción necesaria frente a la inocencia. Al llegar la década de 1930, el valor de este enfoque más riguroso se hacía evidente. Treinta años después era dominante casi por completo. Podría escribirse todo un libro acerca de este periodo en el desarrollo de nuestra disciplina y eso es lo que han hecho algunos autores. Aquí voy a centrarme en un tema derivado: las curvas continuas y el concepto de dimensión.

 

*

 

Es probable que el concepto de curva se remonte al momento en el que algún humano primitivo arrastró por primera vez la punta de un palo a través de una superficie de arena o barro y descubrió que dejaba una marca. Empezó a adquirir su forma actual cuando la manera lógica de abordar la geometría echó a volar en la antigua Grecia y Euclides afirmó que un punto tiene solo posición y que una línea carece de anchura. Una curva es una línea que no necesita ser recta. El ejemplo más sencillo es una circunferencia o un arco de la misma. Los griegos desarrollaron y analizaron varias de ellas, las ya mencionadas: elipse, cuadratriz, cicloide, etcétera. Solo tomaron en consideración ejemplos concretos, pero la idea general era «más o menos evidente».

Tras la introducción del cálculo, cobraron relevancia dos propiedades de las curvas. Una de ellas era la continuidad: una curva es continua si no tiene interrupciones. La otra, menos evidente, era la suavidad: una curva es suave si no tiene picos abruptos. El cálculo integral funciona bien para las curvas continuas y el diferencial lo hace para las suaves (esta descripción es muy chapucera para no interrumpir el ritmo de la narración, pero puedo garantizar que se aproxima más a la verdad que a las noticias falsas). Por supuesto, no era tan sencillo: había que definir «interrupción» y «pico» y hacerlo con precisión. De manera más sutil, cualquier definición propuesta tenía que ser adecuada para el estudio matemático y estar planteada en los términos de la disciplina. Había que poder emplearla. Los detalles todavía desconciertan a los estudiantes universitarios la primera vez que se topan con ellos, así que los voy a evitar aquí.

El segundo concepto fundamental es el de dimensión. Todos hemos aprendido que el espacio tiene tres dimensiones, el plano, dos y la línea, una. No se llega a esta noción a partir de una definición del término «dimensión» y un posterior recuento de cuántas hay en el espacio o en un plano. No exactamente. En su lugar, decimos que el espacio tiene tres porque es posible indicar cualquier posición con el empleo de solo tres números. Se designa algún punto concreto como origen y se eligen tres direcciones: de norte a sur, de este a oeste y de arriba abajo. Después solo hay que medir la distancia desde el origen hasta la posición a indicar en cada una de estas direcciones. Esto da tres números (las coordenadas relativas a esas direcciones elegidas) y cada posición en el espacio se corresponde con uno, y solo uno, de estos tríos de números. De manera similar, un plano tiene dos dimensiones porque es posible ahorrarse una de estas coordenadas (digamos la de arriba abajo) y una línea tiene una dimensión.

Todo parece bastante sencillo hasta que se empieza a reflexionar sobre ello. El párrafo anterior asume que el plano en cuestión es horizontal. Por eso es posible prescindir de la coordenada arriba abajo. Pero ¿qué pasa si está en una pendiente? Entonces la dirección perpendicular cobra importancia. No obstante, resulta que el número que indica la vertical viene siempre determinado por los otros dos (siempre que se sepa la inclinación de la pendiente). De modo que lo importante no es la cantidad de direcciones a lo largo de las cuales se midan las coordenadas, sino el número de ellas que son independientes. Es decir, que no son combinaciones de otras direcciones.

Ahora todo se complica un poco más porque no basta con contar cuántas coordenadas hay. Se trata más bien de determinar el menor número que hay que utilizar de ellas. Y esto plantea otra pregunta más profunda: ¿cómo se sabe que dos es de verdad la cantidad más pequeña que hay que emplear para un plano? Podría ser verdad (y si no lo es, se necesita una definición mejor), pero no es evidente. Con esto se abre la veda. ¿Cómo se sabe que tres es la cantidad más pequeña que hay que emplear para el espacio? ¿Cómo se sabe que cualquier elección de direcciones independientes siempre da tres números? Por lo que a esto respecta, ¿hasta qué punto se tiene la certeza de que tres coordenadas son suficientes?

Esta última pregunta es en realidad competencia de la física experimental y conduce, a través de Einstein y su teoría general de la relatividad, a inferir que el espacio físico no es, de hecho, el espacio plano tridimensional de Euclides, sino una versión curva. O, si la teoría de cuerdas está en lo cierto, que es un espacio-tiempo que tiene diez u once dimensiones, todas las cuales, excepto cuatro, son demasiado pequeñas para percibirlas o son inaccesibles. La primera y la segunda pregunta pueden resolverse de manera satisfactoria, aunque no sean triviales, con solo definir el espacio euclídeo tridimensional en términos de un sistema de coordenadas con tres números y pasando luego de cinco a seis semanas en un curso universitario de espacios vectoriales, en los que es posible cualquier número de coordenadas, para demostrar que las dimensiones de un espacio vectorial son únicas.

Un aspecto inherente al enfoque del espacio vectorial es la noción de que un sistema de coordenadas se basa en líneas rectas y que el espacio es plano. De hecho, se conoce también como «álgebra lineal». ¿Qué pasa si nos marcamos un Einstein y permitimos que el sistema de coordenadas no sea recto? Bueno, si se dobla de una manera suave (lo que se conoce tradicionalmente como «coordenadas curvilíneas») no hay problema. Pero en 1890, el matemático italiano Giuseppe Peano descubrió que si se tuerce de una manera brusca (tanto que ya no sea suave, aunque no deje de ser continuo), entonces un espacio de dos dimensiones puede tener un sistema de coordenadas con un solo número. Lo mismo vale si es tridimensional. En esta configuración más general y flexible, de repente «el» número de dimensiones se hace cambiante.

Una manera de reaccionar ante este extraño descubrimiento es desdeñarlo. No hay duda de que se deben emplear coordenadas suaves, o algo así. Pero resultó que era mucho más útil y creativo, y también más divertido, aceptar lo inaudito y ver lo que podía ocurrir. Los críticos tradicionalistas eran bastante puritanos y no querían que las nuevas generaciones se lo pasasen bien.

 

*

 

Vamos al grano. Lo que Peano había descubierto (o construido) era una curva continua que pasaba a través de cada punto en un cuadrado. No solo en su perímetro. Eso es fácil. También por todos los que hay en su interior. Y debe pasar de manera exacta por cada uno de ellos, no solo aproximarse mucho.

Supongamos que existe una curva así. Entonces no es más que algún tipo de línea ondulante, que tiene su propio sistema de coordenadas intrínseco (qué distancia se debe recorrer sobre ella). Eso es un solo número, de modo que la curva es unidimensional. No obstante, si pasa a través de todos los puntos de una superficie cuadrada, que tiene dos dimensiones, se habrá conseguido especificar cada punto de ese cuadrado con una única coordenada que varía de manera continua. ¡De modo que la superficie es en realidad unidimensional!

Intento evitar por norma los signos de exclamación cuando escribo, pero este descubrimiento los merece. Es una locura. También es verdad.

Peano había encontrado el primer ejemplo de lo que ahora se conoce como una curva que «recubre el espacio». Su existencia se basa en la distinción, sutil pero crucial, entre curvas suaves y continuas. Estas últimas pueden ser ondulantes. Las suaves... no. Por lo menos no así de ondulantes.

Peano tenía la actitud adecuada para construir su curva. Le gustaban las disquisiciones sobre detalles lógicos. También fue el primero en escribir axiomas precisos para el sistema de los números naturales (una lista sencilla de propiedades que especifican ese sistema con precisión). No construyó su curva solo por diversión: daba los toques finales a la obra de otro predecesor de inclinaciones parecidas, que también tenía un profundo interés en la naturaleza de los números naturales y en lo que significa contar. Su nombre era Georg Cantor y lo que le interesaba de verdad era el infinito. La mayoría de los matemáticos destacados de la época repudiaban las ideas radicales y brillantes de Cantor, lo que le llevó a la desesperación. Es probable que el rechazo no fuese la causa de su posterior enfermedad mental, como se ha sugerido a veces, pero no cabe duda de que no le hizo ningún bien. Entre los pocos matemáticos reconocidos que supieron apreciar lo que Cantor intentaba hacer se encontraba uno que escaló las cumbres de la disciplina hasta sus cimas más elevadas: David Hilbert. Puede que Hilbert fuera el matemático más destacado de su época y, más tarde en su vida, se convirtió en uno de esos pioneros de la lógica matemática y de los fundamentos de la disciplina. Tal vez reconoció en Cantor a un alma gemela.

En cualquier caso, todo empezó con Cantor y con su introducción de los cardinales transfinitos (cómo contar cuántos elementos hay en un conjunto infinito). Su demostración de que algunos infinitos son mayores que otros es famosa. Más en concreto, no existe una correspondencia biyectiva entre los números enteros y los reales. Buscaba un cardinal transfinito que fuese mayor que el de estos últimos y durante un tiempo estuvo convencido de que el cardinal del plano debía ser más grande que el de la línea. En 1874, escribió a Richard Dedekind:

¿Es posible hacer corresponder unívocamente una superficie (digamos un cuadrado incluyendo su frontera) con una línea (digamos un segmento de recta incluyendo sus puntos extremos), de manera unívoca tal que a cada punto de la superficie le corresponda un punto de la línea, e inversamente a cada punto de la línea un punto de la superficie?

En este momento tengo la impresión de que la respuesta a esta pregunta (si bien uno se ve aquí tan inclinado al no, que podría parecerle casi superflua la demostración) ofrece graves dificultades.

Tres años más tarde escribió de nuevo para decir que estaba equivocado. Muy equivocado. Había encontrado una correspondencia biyectiva entre el intervalo unidad y el espacio de n dimensiones para cualquier n finito. Es decir, una manera de hacer corresponder los miembros de ambos conjuntos entre sí de forma que cada elemento de uno de ellos se correspondiera exactamente con uno solo del otro conjunto. «Lo veo», escribió Cantor, «pero no lo creo».

La idea principal es sencilla: dados dos puntos en el intervalo unidad (entre 0 y 1) es posible escribirlos en decimales como:

x = 0 · x1x2x3x4...

y = 0 · y1y2y3y4...

y hacer que esto corresponda a un punto en el intervalo unidad cuya expansión decimal sea

0 · x1y1x2y2x3y3x4y4...

al intercalar las posiciones decimales, del mismo modo que se hace con los naipes de las dos mitades de un mazo de cartas.7 La principal diferencia es que la baraja de Cantor es infinita. Ahora bien, cuando se mezclan entre sí dos mazos infinitos se obtiene una baraja infinita. Así es como Cantor consigue reunir dos coordenadas en una. Para gestionar tres dimensiones no hay más que usar tres barajas, etcétera.

Cantor publicó algunos de estos resultados en 1878. Investigó los conjuntos numerables, que pueden ponerse en correspondencia biyectiva con los números naturales, así como aquellos conjuntos que tienen este tipo de relación entre sí. También se dio cuenta de que su correspondencia entre el intervalo unidad y el cuadrado unidad no conserva las dimensiones (se pasa de dos a una) y, lo que es más importante para nuestra historia, insistió en que la correspondencia que había construido no es continua. Es decir, puntos muy próximos entre sí en el intervalo unidad no tienen por qué corresponder a puntos muy próximos en el cuadrado unidad.

Las ideas de Cantor eran muy controvertidas y algunos matemáticos eminentes las consideraron un sinsentido, con toda probabilidad porque eran tan originales que requerían imaginación y una mente abierta para apreciarlas. Otros, sobre todo Hilbert, declararon que la nueva rama de la disciplina que había inaugurado Cantor era un «paraíso». El reconocimiento completo de la importancia de su obra solo llegó tras su fallecimiento.

 

*

 

En 1879, Eugen Netto8 dio respuesta a una pregunta evidente al demostrar que no existe una correspondencia biyectiva continua entre el intervalo unidad y la superficie cuadrada unidad, algo que es más difícil de lo que parece a primera vista. El logro más significativo se produjo en 1890, cuando Peano soltó el zorro en el gallinero con su curva que recubría el espacio y demostró que nuestra imagen mental por defecto de una curva continua puede ser engañosa en extremo.

Izquierda: una etapa temprana en una interpretación geométrica de la curva que recubre el espacio de Peano. Derecha: una etapa temprana en la construcción de la curva que recubre el espacio de Hilbert.

No hay ilustraciones en el artículo de Peano. Define la curva mediante el empleo de expansiones ternarias de puntos en el intervalo unidad y su construcción es similar a la geometría que se muestra, arriba, en la imagen de la izquierda.9 En 1891, Hilbert publicó otro ejemplo de curva que recubre el espacio, con un trazo similar a la figura de la derecha. Ambas construcciones son bastante complejas. Las ilustraciones muestran etapas tempranas de un proceso iterativo en el que se sustituyen de manera repetida polígonos sencillos por otros más complicados. Desde entonces se han descubierto muchas otras curvas que recubren el espacio.

Este tipo de curvas tienen aplicaciones en informática, tales como el almacenamiento y la recuperación de datos multidimensionales.10 La idea básica es que es posible recorrer una matriz de varias dimensiones al seguir una aproximación a una curva que recubre el espacio, lo que reduce los problemas al caso unidimensional. Otra aplicación proporciona una solución rápida, aunque no sea exacta, al problema de la persona viajante. La idea es ejecutar una aproximación finita a una curva que recubre el espacio a través de la región que contiene las ciudades, ordenar estas a lo largo de la línea y después visitarlas en ese orden mediante la trayectoria de menor longitud que las une en cada paso. Con esto se obtiene un recorrido que no suele ser más de un 25 % mayor que el caso óptimo.11

¿Qué otras formas pueden recubrir una curva? Es posible extender la construcción de Hilbert a tres dimensiones y obtener una curva que recubra el cubo unidad, mientras que otras también pueden recubrir hipercubos de una cantidad cualquiera de dimensiones. El último grito es un teorema demostrado por Hans Hahn y Stefan Mazurkiewicz, que caracteriza por completo los espacios topológicos que puede recubrir una curva.12 Resulta que son casi cualesquiera, siempre que sean compactos (con extensión finita) y cumplan unas cuantas condiciones técnicas que descartan espacios inverosímiles.

 

*

 

La persona viajante puede tener todavía la última palabra. En 1992, Sanjeev Arora y colaboradores13 descubrieron que la clase de complejidad NP («comprobable con facilidad») tiene una curiosa propiedad que arroja dudas sobre cualquier expectativa de hallar algoritmos de clase P («calculable con facilidad») que den buenas soluciones aproximadas. Demostraron que si P ≠ NP y el tamaño del problema es superior a cierto umbral, entonces calcular una buena aproximación a la respuesta no es más fácil que encontrar esta en sí misma. La única alternativa a esta conclusión sería que P = NP, lo que valdría un millón de dólares, pero de momento tiene que permanecer como hipótesis.

Su aportación está relacionada con una idea notable de verdad: las demostraciones holográficas. Las demostraciones son la esencia de las auténticas matemáticas. En la mayoría de las ramas de la ciencia las teorías pueden contrastarse con la realidad, mediante observaciones o experimentos. Ese lujo no está disponible en matemáticas, aunque todavía hay una manera de verificar sus resultados. En primer lugar, estos deben venir respaldados por una demostración lógica. Después, hay que comprobar esta para garantizar que no contiene errores y que no se ha pasado nada por alto. Es difícil alcanzar este ideal y, de hecho, no es lo que hacen los investigadores en realidad, aunque ese sea su objetivo. Todo aquello que no supera esta prueba se califica de manera inmediata como «erróneo», aunque todavía puede ser útil como paso hacia una demostración mejor que sea correcta. De modo que, desde los tiempos de Euclides hasta la actualidad, los matemáticos han gastado mucho tiempo en repasar con cuidado las demostraciones, tanto las propias como las de los demás, renglón a renglón, en busca de elementos con los que estuviesen de acuerdo y de otros para los que no les salieran las cuentas.

En los últimos años ha surgido una manera diferente de hacer las comprobaciones: emplear ordenadores. Esto exige volver a escribir las demostraciones en un lenguaje que los ordenadores puedan procesar mediante algoritmos. Funciona y ha conseguido éxitos espectaculares con algunos de los problemas más difíciles que se conocen, aunque hasta el momento no ha desplazado a otros métodos más tradicionales. Un efecto secundario de esta idea es un enfoque renovado en la forma de presentar las demostraciones de manera asequible para los ordenadores, que a menudo es diferente por completo de cualquier cosa que pueda digerir un humano. Los procesadores no se quejan si se les dice que repitan la misma operación millones de veces ni que comparen dos filas de miles de dígitos binarios para asegurarse de que son idénticas. Se ponen manos a la obra sin más.

A los matemáticos humanos les gustan más las demostraciones que cuentan una historia, con principio, trama y final evidentes y con una narración atractiva que los lleve desde el punto de partida, las hipótesis del teorema, hasta su conclusión. El relato es más importante que las disquisiciones lógicas. El objetivo es ser claro, conciso y por encima de todo, convincente. Hay que tener en cuenta que la dificultad de convencer a un matemático es notoria.

A los informáticos teóricos que estudian las demostraciones comprobables por ordenador se les ocurrió un enfoque totalmente diferente: las demostraciones interactivas. En lugar de presentarlas como un relato, escritas por un investigador y leídas por otro, esta nueva perspectiva las convierte en un enfrentamiento. Un matemático, con el tradicional nombre de Pat, quiere convencer a Vanna de que su demostración es correcta y Vanna quiere persuadirle de que no lo es. Intercambian preguntas y respuestas entre sí hasta que uno de ellos admite la derrota (Pat Sajak y Vanna White eran personajes famosos en la televisión estadounidense que salían en el programa La ruleta de la fortuna). Es como una partida de ajedrez, en la que Pat anuncia «jaque mate en cuatro jugadas». Vanna no está de acuerdo, así que Pat hace un movimiento. Vanna replica con un «¿qué pasa si hago esto?» y Pat mueve de nuevo. Este tira y afloja sigue hasta que Vanna pierde. Ahora ella empieza a dar marcha atrás. «Supongamos que mi última jugada hubiese sido esta en lugar de la anterior.» Pat hace un movimiento diferente y ¡jaque mate! Se continúa así hasta que se agotan todas las posibles respuestas de Vanna ante las jugadas de Pat y este gana, o bien hasta que él se ve obligado a admitir que en realidad no era jaque mate en cuatro jugadas. Según mi experiencia, justo esto es lo que hacen los matemáticos en la vida real cuando trabajan juntos para resolver un problema en una investigación y los ánimos pueden llegar a calentarse. La versión en forma de relato de la solución a la que se llega en última instancia es la que se presenta en un seminario.

Laszlo Babai y otros se valieron de este tipo de técnica de demostración argumentativa para llegar a la noción de demostración holográfica mediante el empleo de herramientas matemáticas tales como polinomios sobre campos finitos y códigos de corrección de errores.14 Una vez establecidos estos métodos, se dieron cuenta de que los ordenadores pueden aprovechar una característica que se evita en aras de la claridad y la concisión: la redundancia. Resulta que una demostración lógica puede volverse a escribir en una forma que la hace mucho más larga, pero que implica también que si hay un error aparece casi por todas partes. Cada paso del argumento se extiende por toda la demostración en muchas copias relacionadas casi idénticas. En cierto modo es como un holograma, en el que se transforma una imagen de manera que puede reconstruirse a partir de cualquier porción pequeña de los datos. En esos casos, la demostración puede comprobarse con solo tomar una pequeña muestra aleatoria. Cualquier error aparecerá casi con total seguridad en ella. Si se hace así, se tiene una demostración holográfica. El teorema acerca de la inexistencia de soluciones aproximadas de clase P es una consecuencia.

 

*

 

Volvamos al artículo de la paloma de Gibson, Wilkinson y Kelly en Animal Cognition. Parten de la afirmación de que el TSP se había empleado hacía poco para examinar aspectos del conocimiento humano y animal, sobre todo de la capacidad de planificar acciones antes de emprenderlas. No obstante, no estaba claro si esta habilidad estaba limitada a los primates. ¿Pueden hacerlo también otros animales o solo siguen reglas rígidas, desarrolladas al evolucionar? Los investigadores decidieron emplear palomas en pruebas de laboratorio que las situaban ante TSP sencillos que tenían dos o tres comederos de destino. Las aves empezaban en una ubicación, visitaban cada comedero en algún orden y continuaban hasta un destino final. El equipo concluyó que «las palomas sopesaban con detenimiento la proximidad de la siguiente ubicación, pero parecían planificar varios pasos por adelantado cuando aumentaba el coste del desplazamiento a causa del comportamiento ineficaz. Los resultados proporcionan una evidencia clara y firme de que los animales, aparte de los primates, son capaces de planificar recorridos de desplazamiento sofisticados».

En una entrevista, los investigadores explicaban la relación con la paloma conductora de autobús. Sugerían que el humano podría tener dos razones para poner pegas: la evidente de la seguridad y la preocupación de que el ave fuera incapaz de seguir una ruta para recoger a los pasajeros de manera eficaz conforme el autobús atravesaba la ciudad. Como afirma el título del artículo, el equipo llegaba a la conclusión a partir de sus experimentos de que la segunda preocupación no estaba justificada.

¡Deja que la paloma conduzca el autobús!

 

*

 

Si los gobiernos mundiales y los fabricantes de coches se salen con la suya, pronto ni el humano ni la paloma conducirán nada. Será el autobús el que conduzca el autobús en su lugar. Nos adentramos en una era feliz de vehículos autónomos.

O tal vez no.

El aspecto más difícil de lograr en los vehículos sin conductor es garantizar que interpretan su entorno de manera correcta. Dotarles de sus propios «ojos» es fácil, porque en la actualidad se fabrican miles de millones de pequeñas cámaras de alta resolución. Pero la visión necesita un cerebro tanto como unos ojos, de modo que coches, camiones y autobuses se equipan con software de visión por ordenador. Así pueden saber qué es lo que ven y reaccionar de manera acorde.

Según los fabricantes, una ventaja potencial de los vehículos autónomos es la seguridad. Los conductores humanos cometen errores y causan accidentes. Un procesador no se distrae y, con bastante investigación y desarrollo, un ordenador debería ser más seguro al volante que cualquier persona. Otro aspecto positivo es que no hay que pagar al autobús para que se conduzca a sí mismo. Una gran desventaja, aparte de hacer que los conductores pierdan su empleo, es que esta tecnología se halla todavía en pañales y que los sistemas disponibles en la actualidad no están a la altura de las expectativas que generan. Ya han fallecido algunos peatones y conductores de prueba en accidentes y, sin embargo, en la actualidad se siguen ensayando vehículos completamente autónomos en las calles de las ciudades de varios países. El argumento es que deben probarse en el mundo real y que, en última instancia, salvarán más vidas de las que pueden costar. La facilidad con la que los reguladores se han dejado convencer por este seductor razonamiento es notable. Si alguien sugiriese probar un nuevo medicamento en pacientes aleatorios, sin su conocimiento ni consentimiento, alegando que esto salvará a más personas de las que va a matar, se armaría un escándalo. De hecho, sería ilegal en casi todos los países y es sin duda contrario a la ética.

A este respecto, la tecnología principal tras la visión por ordenador es el campo, aún más de moda, del aprendizaje autónomo. Una red de aprendizaje profundo, que ajusta sus fuerzas de conexión de modo que identifica figuras de manera correcta, se entrena con una cantidad enorme de imágenes hasta que alcanza un nivel aceptable de precisión. Este procedimiento ha tenido un éxito enorme en un amplio rango de aplicaciones. No obstante, en 2013 se hizo evidente que se prestaba demasiada atención a los éxitos del aprendizaje autónomo y muy poca a sus fallos potenciales. Un problema grave son los «ejemplos contradictorios», que son representaciones modificadas de manera deliberada para que un humano acierte mientras que un ordenador comete fallos espectaculares.

Estas dos imágenes, que difieren solo en unos pocos píxeles, se mostraron a la red Inception V3, que clasificó la de la izquierda como un gato y la de la derecha como guacamole.

La fotografía muestra dos imágenes de un gato. Obvio. Solo se diferencian en unos pocos píxeles y son idénticas a nuestros ojos. Una red neuronal estándar, entrenada con cantidades enormes de figuras de gatos y de lo que no son gatos, identifica de manera correcta la imagen de la izquierda como tal. Sin embargo, insiste en que la de la derecha es guacamole, la salsa mexicana verde hecha de aguacate. Es más, alcanza una certeza del 99 % de que es guacamole, en comparación con solo un 88 % para el gato. Como dice el dicho, un ordenador es un aparato para cometer millones de errores muy rápido.

Se dice que imágenes de este tipo son «contradictorias» porque surgen cuando alguien intenta engañar al sistema de manera deliberada. En la práctica, la red identificará un gato en la mayoría de las fotografías como estas. Christian Szegedy y sus colaboradores se dieron cuenta en 2013 de que existían estas imágenes.15 En 2018, Adi Shamir y sus colegas16 explicaron por qué es posible producir ejemplos contradictorios en sistemas de aprendizaje profundo, por qué son inevitables y por qué basta con cambiar unos pocos píxeles para despistar a la red neuronal.

La causa fundamental de esta susceptibilidad a errores graves es la extensión. La manera habitual de medir cómo son de diferentes dos cadenas de código binario es calcular su distancia de Hamming, el número de bits que es necesario cambiar para convertir una en la otra. Por ejemplo, este parámetro para 10001101001 y 10101001111 es cuatro, con los bits diferentes resaltados en negrita en 10101001111. Una fotografía está representada en el ordenador por una cadena binaria muy larga. Si la imagen ocupa 1 MB (megabyte), su longitud es 2²³, o cerca de 8 millones de bits. De modo que el espacio de las imágenes tiene una extensión de 8 millones sobre el campo finito que consiste en 0 y 1. Contiene 2^8.388.608 puntos diferentes.

El algoritmo de reconocimiento de figuras incorporado a una red neuronal entrenada tiene que situar cada imagen de este espacio en un número mucho más pequeño de categorías. En el caso más sencillo, esto se reduce a dividir el espacio de las imágenes en regiones mediante la creación de hiperplanos, un procedimiento que se ilustra en la fotografía para dos dimensiones. Esto reparte el espacio en numerosas celdas, una para cada categoría. Si se cambia la imagen a una que esté a una distancia de Hamming de, pongamos, 40, entonces solo hay que sustituir 40 elementos en la cadena. El ojo percibe 8 millones de bits, por lo que la diferencia supone apenas el 0,0005 % del total, muy por debajo del umbral a partir del que un humano notaría alguna diferencia significativa. No obstante, el número de imágenes dentro de esta distancia de Hamming es de 2⁵⁰, en torno a los mil billones. Esta cantidad es mucho mayor que el total de las categorías que puede distinguir el sistema de visión por ordenador. De modo que no resulta sorprendente que un cambio tan pequeño en la imagen pueda llevar a la red a malinterpretarla.

Para el análisis matemático es conveniente representar las cadenas de bits no sobre un campo finito sino como números reales. Por ejemplo, un solo byte de 8 bits, digamos 10001101, puede considerarse como el número real con expansión binaria 0,10001101. Ahora el espacio de todas las imágenes de 1 MB se convierte en un espacio vectorial real de extensión un millón. Con esta modificación, Shamir y sus colegas demostraron algo mucho más determinante. Dada una fotografía en una celda de la disposición de hiperplanos y dada una segunda celda, ¿cuántos bits hay que cambiar en la imagen para llevarla hasta esta última? Su análisis demuestra que, por ejemplo, si el espacio de imágenes está dividido en un millón de categorías mediante 20 hiperplanos, entonces solo hay que cambiar dos coordenadas para mover un punto dado a cualquier celda, siempre que la extensión del espacio de imágenes sea mayor que 250. En general, si se ha entrenado a la red para que distinga un número dado de categorías, la cantidad de coordenadas que debe cambiarse para mover una imagen dada a cualquier celda es más o menos el mismo que el número de estas.

División del espacio de la imagen por hiperplanos. En este caso, hay dos dimensiones y cinco hiperplanos (aquí, rectas) dividen el espacio en trece celdas. Una se muestra sombreada.

Comprobaron su teorema en un sistema comercial de reconocimiento de números. En este caso hay diez categorías, que son los dígitos de 0 a 9. Produjeron imágenes contradictorias para persuadir al sistema de que reconociese el 7 como cualquiera de las diez posibilidades, de 0 a 9. Solo había que cambiar 11 bits para lograrlo y lo mismo vale para cualquier dígito que no sea el 7.

¿Deberíamos preocuparnos? Las imágenes «naturales», del tipo que encontrarán de manera habitual los vehículos autónomos, no se construyen de forma deliberada para engañar al sistema. No obstante, el coche percibirá a su alrededor en torno al medio millón de imágenes al día y basta con una interpretación errónea para que se produzca un accidente. La amenaza principal es que gamberros o terroristas puedan modificar fácilmente las señales de tráfico con solo añadir pequeños trozos de cinta negra o blanca y engañar así al ordenador para que piense que una señal de stop es en realidad un límite de velocidad de 90 kilómetros por hora. Todo lo cual contribuye a la impresión de que la introducción de los coches autónomos se hace de manera apresurada, indebida e insegura a causa de presiones comerciales. Si alguien no está de acuerdo, me permito repetir: nunca se introduciría un fármaco o procedimiento médico nuevos de forma tan chapucera. Sobre todo si hay buenas razones para sospechar que puede ser peligroso.

¡No dejes que el autobús conduzca el autobús!