UN DISCO LLENO PRESTADO HACE MÁS RÁPIDOS LOS ORDENADORES
Algunos problemas son baratos en tiempo pero voraces en memoria; otros, al revés. Para unas pocas tareas básicas, los teóricos han demostrado límites estrictos a ese compromiso: con una memoria de trabajo pequeña, no se puede ser rápido. Un nuevo artículo muestra que un recurso extraño, una memoria que ya está llena y debe devolverse intacta, rompe esos límites.
El disco duro prestado
El modelo se llama computación catalítica y lo introdujeron en 2014 Buhrman, Cleve, Koucký, Loff y Speelman. Un algoritmo dispone de una minúscula memoria limpia, del orden de log n bits para una entrada de tamaño n, más una enorme memoria sucia ya llena de datos arbitrarios que no ha elegido. Puede usar ambas como quiera, pero al terminar, cada bit de la memoria sucia debe estar exactamente como estaba.
Los autores recurren a la imagen clásica: tomas prestado el enorme disco duro de un amigo, lleno de valiosos recuerdos digitales, para hacer un cálculo. No quieres perder a un amigo, así que al terminar restauras cada bit.
Al principio, el modelo pretendía demostrar que una memoria así no sirve para nada. Intuitivamente, para restaurarlo todo hay que conservar toda la información, de modo que nunca se libera espacio. Sorprendentemente, resultó ser cierto lo contrario: la memoria llena permite resolver problemas que nadie sabe resolver solo con memoria limpia. Pero esos resultados se referían al espacio, y los algoritmos eran extremadamente lentos.
Más rápido de lo que es demostrablemente posible
Adelmo Morrison Orozco, Nathan Sheffield y Ryan Williams (MIT) se fijan ahora en la velocidad. Con memoria limpia logarítmica y una cantidad polinómica de memoria prestada, presentan algoritmos que:
- ordenan una lista y calculan una transformada discreta de Fourier en tiempo n^(1+o(1)), casi lineal;
- multiplican matrices en tiempo n^(ω+o(1)), tan rápido como el mejor método conocido con memoria ilimitada.
Sin el disco prestado, está demostrado que el producto del tiempo por la memoria debe ser al menos del orden de n² para la ordenación y la transformada de Fourier, y de n³ para la multiplicación de matrices. Así que estos algoritmos catalíticos alcanzan velocidades que ningún algoritmo ordinario con poca memoria puede alcanzar. Los autores lo califican como la primera demostración incondicional de que los algoritmos catalíticos superan a sus equivalentes no catalíticos.
Conmutar, leer, deshacer
El ingrediente clave es un breve truco combinatorio. Supongamos que un algoritmo puede hacer que una sección de la memoria prestada alterne entre un valor desconocido τ y τ + x, donde x es el resultado que le interesa. En una gran tabla «auxiliar», también prestada, se suma 1 a un conjunto de entradas cuidadosamente elegido. La entrada en la posición τ aumenta en uno si y solo si x pertenece a un conjunto dado. Después se ejecuta cada paso hacia atrás, y el disco queda como antes, salvo por el bit de respuesta que se buscaba.
Apilando este truco capa a capa se evalúan rápidamente circuitos poco profundos. Los autores reformulan entonces las redes de ordenación, las transformadas rápidas de Fourier y la multiplicación rápida de matrices como circuitos de ese tipo. En aritmética, solo las capas que multiplican dos incógnitas tienen un coste adicional; las capas puramente lineales salen casi gratis.
Una comparación justa
Una objeción: los límites clásicos suponen que la respuesta se escribe una sola vez, de izquierda a derecha, en una cinta de salida separada, mientras que los algoritmos catalíticos escriben su respuesta en el disco prestado. El artículo responde a ello. Los autores muestran que sus algoritmos pueden escribir la respuesta en dos pasadas sobre una cinta de salida, y que para los algoritmos ordinarios dos pasadas no ayudan más que una. Por tanto, los límites siguen siendo válidos y la separación se mantiene. También demuestran que una sola pasada no basta ni siquiera con el disco prestado: la ordenación choca entonces con la misma barrera de n².
Una larga lista de beneficiarios
Las mismas herramientas dan algoritmos catalíticos rápidos para multiplicar enteros grandes y polinomios, contar triángulos y encontrar cliques en redes, detectar caminos y ciclos, y buscar patrones de texto con comodines. Sus tiempos de ejecución igualan, salvo pequeños factores, los de los mejores algoritmos conocidos que disponen de toda la memoria que quieran. En cada caso, la memoria prestada debe devolverse exactamente como se prestó.