Misterio resuelto: en computación, mucha memoria es mejor que mucho tiempo

Williams comenzó a asistir a las horas de consulta de Hartmanis todas las semanas, donde casi siempre era el único estudiante presente. Su tenacidad dio sus frutos: obtuvo una calificación de sobresaliente en el curso, y Hartmanis aceptó asesorarlo en un proyecto de investigación independiente el semestre siguiente. Sus reuniones semanales continuaron durante toda la etapa universitaria de Williams. Hartmanis lo animó a cultivar un enfoque individualizado en la investigación de la complejidad y lo alejó con delicadeza de los callejones sin salida.

“Estuve profundamente influenciado por él en ese entonces”, recordó Williams. “Supongo que todavía lo estoy”.

Pero a pesar de obtener una codiciada beca de investigación de posgrado de la Fundación Nacional de Ciencias, Williams fue rechazado en todos los programas de doctorado a los que solicitó admisión. Al enterarse de la noticia, Hartmanis llamó a un colega y luego felicitó a Williams por haber sido aceptado en un programa de maestría de un año en Cornell. Un año después, Williams volvió a solicitar admisión a varios programas de doctorado, y con esa experiencia investigadora adicional, alcanzó el éxito.

Williams continuó trabajando en teoría de la complejidad durante sus estudios de posgrado y en los años posteriores. En 2010, cuatro años después de obtener su doctorado, logró un resultado trascendental; un pequeño paso, pero el más grande en décadas, hacia la solución de la pregunta más famosa de la informática teórica: la naturaleza de los problemas complejos. Este resultado consolidó la reputación de Williams, quien posteriormente escribió docenas de artículos sobre diferentes temas de teoría de la complejidad.

Leslie Valiant

P versus PSPACE no fue uno de ellos. Williams había estado fascinado por el problema desde que lo abordó en la universidad. Incluso complementó su currículo de informática con cursos de lógica y filosofía, buscando inspiración en otras perspectivas del tiempo y el espacio, sin éxito.

«Siempre lo he tenido en mente», agregó Williams. “Simplemente no se me ocurría nada lo suficientemente interesante que decir al respecto”.

El año pasado, finalmente encontró la oportunidad que había estado esperando.

Piedras blandas

La historia del nuevo resultado de Williams comenzó con el progreso en una pregunta diferente sobre la memoria en computación: ¿Qué problemas se pueden resolver con un espacio extremadamente limitado? En 2010, el pionero teórico de la complejidad Stephen Cook y sus colaboradores inventaron una tarea, llamada el problema de evaluación del árbol, que demostraron que sería imposible para cualquier algoritmo con un presupuesto de espacio inferior a un umbral específico. Pero existía una laguna. La demostración se basaba en la misma suposición de sentido común que Paul y sus colegas habían hecho décadas antes: los algoritmos no pueden almacenar datos nuevos en un espacio ya lleno.

Durante más de una década, los teóricos de la complejidad intentaron resolver esa laguna. En 2023, el hijo de Cook, James, y el investigador Ian Mertz la desvelaron por completo al idear un algoritmo que resolvía el problema de la evaluación de árboles utilizando mucho menos espacio del que se creía posible. La demostración de Cook padre suponía que los bits de datos eran como pequeñas piedras que deben ocupar lugares separados en la memoria de un algoritmo. Pero resulta que esa no es la única forma de almacenar datos. “De hecho, podemos pensar en estas piedras como cosas que podemos aplastar ligeramente unas sobre otras”, explicó Beame.