Los cálculos requieren tiempo y memoria, han encontrando nuevas maneras de reducir la necesidad de esta última

Comparta este Artículo en:

El tiempo y el espacio son temas frecuentes de debate para los cosmólogos, especialmente para quienes estudian cuerpos celestes exóticos como los agujeros negros, un ámbito donde ambos conceptos se vuelven, como mínimo, un poco confusos. Ahora, un nuevo estudio demuestra que, en términos computacionales, el tiempo y el espacio tienen una relación igualmente compleja.

Por supuesto, a los informáticos no les preocupa la estructura del espacio-tiempo que sustenta nuestra realidad.

Más bien, se interesan por la relación entre la memoria (también conocida como espacio) y el tiempo que se tarda en realizar un cálculo.

En la década de 1970, los teóricos de la complejidad computacional plantearon la hipótesis de que cualquier cálculo que requiriera X cantidad de pasos requeriría X/log X de memoria para completar dicho cálculo.

Si un cálculo requiriera 100 pasos, dado que log 100 es igual a 2, ese cálculo requeriría 50 ranuras de memoria.

Sin embargo, un estudio sorprendente sugiere que se puede ir mucho más allá, y que un cálculo con X pasos podría requerir solo la raíz cuadrada de X log X de memoria.

Si volvemos al ejemplo de X = 100, el número de ranuras de memoria necesarias para ese cálculo se reduce de 50 a aproximadamente 14.

“Una de las preguntas más fundamentales en la informática teórica es: ¿cómo se relaciona el tiempo con el espacio en la computación?”, dice el artículo, escrito por el científico informático teórico del MIT Ryan Williams.

“Hemos demostrado que las máquinas de Turing multicinta y los circuitos tienen algoritmos de evaluación sorprendentemente eficientes en cuanto al espacio, mediante una reducción al problema de evaluación de árbol”.

Desarrollado inicialmente a finales de la década de 2000, el problema de evaluación de árbol “implica la resolución repetida de un problema matemático más simple que convierte un par de números de entrada en una única salida”.

Su nombre proviene de su diseño ramificado, ya que las copias de los problemas se superponen y deben resolverse antes de abordar el problema “raíz”.

Avances recientes han demostrado que es posible reutilizar la memoria de la computadora cuando ya está llena.

Esta idea se conoce como “computación catalítica“, tomando prestado un término químico que describe cómo esta memoria adicional crea una “reacción” computacional, como un catalizador.

Este avance sería como si un humano resolviera un problema complejo de varios pasos utilizando únicamente su memoria a corto plazo.

El modelo de Williams representaba cualquier problema computacional, y una vez aplicado este nuevo algoritmo de evaluación de árboles, demostró una reducción drástica de la memoria requerida.

Sin embargo, Williams declaró que el resultado fue una combinación de “trucos matemáticos” y “cancelaciones mágicas”.

En consecuencia, esto significa que se necesita menos espacio para realizar cálculos, pero el avance no mejora el tiempo: generar soluciones sigue requiriendo el mismo tiempo.

Por ello, es poco probable que el avance de Williams altere fundamentalmente la forma en que usamos las computadoras.

Pero si se descubriera lo contrario, una mayor cantidad de memoria podría acelerar el tiempo de los cálculos.

No hace falta una imaginación desbordante para ver la magnitud de un avance como este, sobre todo en un momento en que el aumento de la velocidad de los procesadores, un concepto conocido como la Ley de Moore, se está ralentizando.

El espacio y el tiempo son la base de nuestra realidad conocida, y lo mismo puede decirse de nuestra realidad computacional.

Fuente: Popular Mechanics