¿Crees que puedes hacerlo? Problemas intratables que parecen tratables

En Impossibility: The limits of Science and the Science of Limits, John D. Barrow dialoga sobre los límites de la capacidad mental humana, aportando ejemplos como la teoría de supercuerdas o los modelos actuales de encriptación. Y sobre estos últimos quería hablar.

Existen una serie de problemas matemáticos, fundamentos de los actuales modelos de encriptación, que por su sencillo planteamiento podrían parecer facilmente resolvibles pero que en el fondo no lo son. Son problemas que, sin ser imposibles, su complejidad requeriría billones de años de cálculos matemáticos para alcanzar una respuesta; son problemas intratables. Y sin embargo nuestro cerebro los percibe tratables.

Aquí les van una serie de ejemplos:

• El problema del vendedor a domicilio consiste en encontrar la ruta óptima para que el viajero pase por todos los nodos (ciudades) recorriendo la menor distancia posible.
  
  Aunque para un circuito de trece ciudades el problema es sencillo de resolver (tan solo hay que probar todas las alternativas hasta encontrar la mejor), la complejidad del enunciado crece exponencialmente. De hecho, el mayor itinerario jamás resuelto contiene 3038 ciudades y se necesitaron más de un año y medio de cálculos computacionales para encontrar la respuesta.
• El puzzle de los monos consiste en una colección de nueve cartas cuadradas donde en cada una de ellas hay dibujadas las mitades de los cuerpos de unos monos coloreados. El objetivo es ordenador el puzzle para que cada mitad coincida con su otra sin importar la posición de las cartas.
  
  ¿Creen que pueden resolverlo? Con un juego de 9 cartas las posibles configuraciones son de 9! = 362.880, buena suerte. Y es que aunque parezca sencillo, con un juego de 36 cartas el número de posibilidades se eleva hasta una cifra de 41 dígitos. Incluso si una computadora hiciese el cálculo a una velocidad de un millón de posibles posiciones por segundo ¡tardaría unos once mil millones de millones de millones de años en encontrar la respuesta! Para que se hagan una idea, se sabe que el universo tiene alrededor de trece mil millones de años.
• El último ejemplo son la torres de Hanoi. El juego es muy conocido desde que apareció la versión para el Iphone pero para quien no lo conozca mejor resumo las reglas. El problema consiste en pasar todas las piezas del palo de la izquierda hasta el palo de la derecha siguiendo dos reglas básicas: “solo se puede mover un disco al mismo tiempo” y ” los discos grandes no pueden estar encima de discos más pequeños”.
  
  Se puede calcular sencillamente el número mínimo de movimientos necesarios para completar el juego siguiendo esta fórmula: 2^N – 1. Donde N son el número de discos.Para que se hagan una idea, en el caso de que hubieran 64 discos , incluso algún experto del juego que se moviera a un movimiento por segundo tardaría unos 412 mil millones de años en mover todas las fichas ¡Eso si no se equivoca en ningún movimiento! Barrow calculó que aunque utilizáramos una máquina que hiciera mil millones de movimientos por segundo, tardaríamos unos 400 años en transferir todas las fichas. Tiempo suficiente para considerar el juego como intratable.

Este tipo de esquemas son muy útiles para encriptar conexiones inalámbricas como las que disponemos en casa (las más corrientes son encriptaciones de 64 dígitos) ya que su complejidad sigue una linea exponencial a medida que el número de variables N (los discos, las cartas con monos, o las ciudades) aumenta.