Los límites de la computación: el coste exponencial

4 mayo, 2015

En una de las historias sobre los orígenes del ajedrez, el inventor del juego lo presenta a un rey de la India, que queda entusiasmado con él. A cambio de su juego, el inventor pide una recompensa aparentemente modesta: 1 grano de trigo por la primera casilla del tablero, 2 por la segunda, 4 por la tercera, 8 por la cuarta, y a sí doblando la cantidad en cada casilla. Sin pensar, el rey accede a la que considera una petición extravagante pero razonable.

Al cabo de una semana, su tesorero le informa alarmado que la cantidad de granos de trigo que tendrían que pagar supera a la riqueza de todo el reino. Y es que con 64 casillas, 2^0 + 2^1 + …. + 2^63 = 2^64 – 1 = 18.446.744.073.709.551.615 granos. Para hacernos una idea, esto son unos 15 billones de toneladas de trigo,  el equivalente a la producción mundial de trigo durante 21.685 años. Hay diferentes versiones sobre el final de la historia: el inventor acaba como nuevo rey, el rey se siente engañado y castiga al inventor, …

Siempre hay quien no confía en las matemáticas y tiene que probarlo a mano. Fuente:  Audrey Penven @ Flickr - Licencia: CC BY-NC-SA 2.0
Siempre hay quien no confía en las matemáticas y tiene que probarlo a mano. Fuente: Audrey Penven @ Flickr – Licencia: CC BY-NC-SA 2.0

A parte de las lecciones que pueden extraerse en el mundo del ajedrez (hacer las cosas sin pensar suele dar malos resultados), podemos extraer algunas lecciones relacionadas en el ámbito de la computación. Existen muchos problemas para los que no tenemos buenos algoritmos, de forma que la solución requiere un tiempo de cálculo o un espacio de memoria que se multiplican por un cierto valor constante con cada nuevo elemento del problema. Por ejemplo, un problema clásico es el de la partición: dado un conjunto de N valores naturales, dividirlo en dos subconjuntos que tengan la misma suma total. Si el conjunto inicial tiene N valores, existen 2^N formas de dividirlo en dos partes: para cada valor hay dos posibilidades: asignarlo al primer subconjunto o al segundo. Sin un procedimiento inteligente que nos permita evitar muchas combinaciones, nos veremos obligados a probar 2^N combinaciones y ver si en alguna coincide la suma de valores para cada subconjunto. Igual que en el tablero de ajedrez, esta progresión exponencial rápidamente queda fuera de nuestro alcance.

Repasemos algunas cifras rápidamente:

– Supongamos que queremos construir una memoria para almacenar información sobre un problema de tamaño N con requisitos de memoria 2^N. Se estima que en el Universo observable hay entre 10^72 y 10^82 partículas. Esto significa que si almacenamos cada bit de información mediante una partícula, podríamos almacenar los datos para N=273, pero el universo se nos quedaría pequeño para problemas con N>273.

– ¿Y qué pasa si el tiempo de cálculo de nuestro algoritmo se dobla con cada nuevo elemento? Se estima que el Universo se originó hace aproximadamente 10^10 años, es decir aproximadamente 10^17 segundos. Un problema que se resolviera en un segundo para N=1 tardaría toda la vida del universo para un modesto N=56. Y no sirve pensar que «siempre podemos calcular más de prisa»: en Física también hay límites inferiores respecto al tiempo (el tiempo de Planck, 10^(-44) segundos). Aunque lográramos resolver el caso N=1 a esta velocidad, sólo podríamos resolver problemas con N= 202 en la vida del universo.

Es posible que nuestro conocimiento del Universo y de las leyes de la Física avancen, pero debemos tener presente que a corto plazo hay problemas que quedarán fuera de nuestro alcance. Por ejemplo, un matemático denominó problemas transcomputacionales a todos aquellos problemas que requieren procesar más de 10^93 bits de información. Este el límite que un ordenador del tamaño del planeta Tierra podría procesar desde el momento en que el planeta se creó. En una época en que sólo se habla de Big Data (con un volumen de datos en constante crecimiento), vale la pena ver donde está situado el listón.

Esto es, claro está, a menos que se encuentren algoritmos mejores (que no tengan este coste exponencial) o que aparezca un nuevo paradigma de cálculo (como puede ser la computación cuántica) que cambie la forma en que buscamos la solución. Pero bueno, de esto ya hablaremos otro día.

(Visited 107 times, 1 visits today)
Autor / Autora
Robert Clarisó Viladrosa
Comentarios
Deja un comentario