Pequeña memoria, gran impacto: Un avance en algoritmos desafía los límites computacionales

El profesor de ciencias de la computación del MIT, Ryan Williams, sospechaba que una pequeña cantidad de memoria podría ser tan útil como mucho tiempo en todas las computaciones posibles. En febrero, publicó su prueba en línea, recibiendo gran acogida en la comunidad científica.

Hasta ahora, los algoritmos conocidos para realizar ciertas tareas requerían una cantidad de espacio aproximadamente proporcional al tiempo de ejecución. Los investigadores asumían que no era posible hacer mejor uso del espacio. Sin embargo, la prueba de Williams estableció un procedimiento matemático para transformar cualquier algoritmo, sin importar lo que haga, en una forma que utilice mucho menos espacio.

Lo más sorprendente es que este resultado, que tiene que ver con lo que se puede calcular con cierta cantidad de espacio, también implica un segundo resultado sobre lo que no se puede calcular en un determinado tiempo. Este segundo resultado no es sorprendente por sí mismo, ya que los investigadores sospechaban que era cierto, pero no sabían cómo probarlo. La solución de Williams, basada en su primer resultado, se siente casi excesiva, como si probar la culpabilidad de un sospechoso de asesinato consistiera en establecer un coartada irrefutable para todos los demás en el planeta.