Conjetura de 50 años sobre espacio versus tiempo en la computación resuelta

Una cuestión central en la teoría de la complejidad computacional es la relación entre P y PSPACE, clases que abarcan problemas resolubles en tiempo y espacio razonables, respectivamente. Intuitivamente, el espacio es un recurso más poderoso que el tiempo porque es reutilizable. Durante 50 años, los investigadores intentaron probar que PSPACE es mayor que P, lo que significa que algunos problemas son imposibles de resolver rápidamente, pero solucionables con espacio limitado. Hopcroft, Paul y Valiant hicieron un descubrimiento en 1975, mostrando que el espacio es ligeramente más poderoso que el tiempo. Sin embargo, este progreso estuvo limitado por el enfoque de 'simulación'. Ryan Williams finalmente rompió el estancamiento con un enfoque innovador, resolviendo el problema de larga data.