P vs. PSPACE: ¿Es el espacio computacionalmente más poderoso que el tiempo?

Una cuestión central en la teoría de la complejidad es la relación entre las clases de complejidad P y PSPACE. P abarca problemas resolubles en un tiempo razonable, mientras que PSPACE trata la complejidad espacial. La creencia predominante es que PSPACE es mayor que P, debido a la reutilización del espacio, a diferencia del tiempo. Probar esto requiere demostrar problemas en PSPACE irresolubles en tiempo polinomial. El artículo relata el avance de 1975 de Hopcroft, Paul y Valiant, mostrando la ligera ventaja del espacio sobre el tiempo, pero el progreso se estancó. El trabajo de Ryan Williams finalmente rompió el estancamiento, ofreciendo nuevas perspectivas para resolver el problema P vs. PSPACE.