Una reciente investigación del científico informático Ryan Williams, del MIT, ha revolucionado la teoría de la computación al demostrar que la memoria (espacio) puede ser un recurso más poderoso que el tiempo para resolver ciertos problemas complejos.
Durante décadas, los científicos creían imposible mejorar la simulación universal desarrollada por Hopcroft, Paul y Valiant en los años 70. Sin embargo, Williams utilizó una técnica inspirada en una simulación con “piedras blandas” (squishy pebbles) que redujo de manera radical el uso de espacio, logrando que su nuevo algoritmo usara solo la raíz cuadrada del tiempo original. Aunque más lento, este avance tiene implicaciones teóricas enormes.
Williams no solo probó que algunos algoritmos pueden usar menos espacio para lograr los mismos resultados que otros que consumen más tiempo, sino que también demostró lo contrario: hay problemas que simplemente no se pueden resolver sin más tiempo que espacio disponible. Es la primera conexión fuerte entre estos dos recursos computacionales en medio siglo.
Este trabajo se considera un paso importante hacia una de las mayores preguntas en computación: la relación entre las clases de complejidad P y PSPACE. Aunque aún no se ha probado que PSPACE es estrictamente más poderosa que P, los hallazgos de Williams podrían allanar el camino hacia esa prueba definitiva.
El legendario Leslie Valiant, al enterarse del avance mientras viajaba en autobús junto a Williams, quedó sorprendido:
“Si logras el mejor resultado en 50 años, claramente estás haciendo algo bien”.
Si bien aún quedan obstáculos para ampliar este descubrimiento, Williams afirma que incluso los resultados inesperados pueden ser más valiosos que los que uno espera:
“A menudo, lo que termino probando es mucho mejor que lo que originalmente quería demostrar”.