Para los algoritmos, la memoria es un recurso mucho más valioso que el tiempo.
La asombrosa demostración de un científico informático representa el primer avance en 50 años sobre una de las preguntas más reconocidas en el ámbito de la informática.
En una tarde de julio de 2024, Ryan Williams se propuso demostrar que estaba equivocado. Dos meses antes, había realizado un descubrimiento notable sobre la relación entre el tiempo y la memoria en la computación, sugiriendo que una cantidad pequeña de memoria podría ser tan efectiva como mucho tiempo en todos los cálculos posibles. Este hallazgo parecía tan improbable que Williams supuso que debía haber un error. Decidió aparcar la prueba y concentrarse en ideas más plausibles. Sin embargo, después de varias horas analizando su trabajo, no pudo identificar ninguna falla.
Williams, teórico de la computación en el Instituto Tecnológico de Massachusetts, empezó a considerar que tal vez, efectivamente, la memoria tenía el poder que él había sugerido. A lo largo de los meses siguientes, elaboró los detalles, revisó cada paso y solicitó retroalimentación de otros investigadores. En febrero, finalmente publicó su prueba en línea, recibiendo amplios elogios. Avi Wigderson, un destacado teórico de la computación en el Instituto de Estudios Avanzados, expresó su admiración al enviarle un correo de congratulaciones.
El tiempo y la memoria son recursos fundamentales en la computación. Hasta ahora, los algorítmicos conocidos para ciertas tareas requerían que el espacio utilizado fuera proporcional al tiempo de ejecución, y se asumía que no había forma de optimizar esto. La prueba de Williams estableció un procedimiento matemático para transformar cualquier algoritmo en uno que utilizara menos espacio, independientemente del tipo de tarea.
Además, este resultado implica otro aspecto: lo que no se puede computar en un tiempo determinado. Aunque este segundo resultado no sorprendió a los investigadores, no sabían cómo probarlo. La solución de Williams, basada en su primer hallazgo, proporciona un nuevo enfoque para abordar uno de los problemas más antiguos en la ciencia de la computación.
Williams, que ha trabajado en teoría de la complejidad computacional, ha tenido un camino significativo. Nacido en una granja en Alabama, encontró interés en la computación desde una edad temprana, cuando se fascinó con un simple programa que generaba fuegos artificiales digitales. A medida que creció, se trasladó a una escuela de matemáticas y ciencias donde se dio cuenta del enfoque teórico de la computación.
Superando obstáculos en su carrera académica, Williams finalmente se unió a Cornell, donde fue influenciado por Juris Hartmanis, un pionero en el campo de la teoría de la complejidad. A lo largo de su carrera, Williams se ha centrado en la relación entre el tiempo y el espacio, aunque sus avances habían sido lentos hasta el año pasado, cuando se produjo un cambio tras un descubrimiento que abrió un nuevo camino.
En 2023, un nuevo enfoque de almacenamiento de datos, que permitía una gestión más eficiente de la memoria, llevó a Williams a investigar cómo aplicar esta técnica a la simulación universal. El resultado fue una prueba que no solo estableció que se puede resolver todo problema que use un poco menos de espacio que el requerido por un tiempo ligeramente mayor, sino que también demuestra que algunos problemas no pueden resolverse sin más tiempo que espacio. Este progreso refleja un avance significativo en el campo tras medio siglo de estancamiento.
La obra de Williams no solo ha transformado su campo, sino que también ha creado un nuevo camino potencial para resolver problemas persistentes en la teoría de la complejidad y, posiblemente, en otras áreas de la computación.
