Ese resultado clásico fue una forma de transformar cualquier algoritmo con un presupuesto de tiempo determinado en un nuevo algoritmo con un presupuesto espacial ligeramente más pequeño. Williams vio que una simulación basada en guijarros blandos haría que el uso del espacio del nuevo algoritmo sea mucho más pequeño, casi igual a la raíz cuadrada del presupuesto de tiempo del algoritmo original. Ese nuevo algoritmo de eficiencia espacial también sería mucho más lento, por lo que no era probable que la simulación tuviera aplicaciones prácticas. Pero desde un punto de vista teórico, fue nada menos que revolucionario.
Durante 50 años, los investigadores asumieron que era imposible mejorar la simulación universal de Hopcroft, Paul y Valiant. La idea de Williams, si funcionó, no solo vencería su récord, lo demolería.
“Lo pensé y pensé, ‘Bueno, eso simplemente no puede ser cierto'”, dijo Williams. Lo dejó de lado y no volvió a eso hasta ese fatídico día de julio, cuando intentó encontrar el defecto en la discusión y falló. Después de darse cuenta de que no había defecto, pasó meses escribiendo y reescribiendo la prueba para dejarla lo más claro posible.
A finales de febrero, Williams finalmente Pon el papel terminado en línea. Cook y Mertz estaban tan sorprendidos como todos los demás. “Tuve que dar un largo paseo antes de hacer cualquier otra cosa”, dijo Mertz.
Valiant obtuvo una vista previa de la mejora de Williams en su resultado de décadas durante su viaje matutino. Durante años, ha enseñado en la Universidad de Harvard, justo al final de la oficina de Williams en el MIT. Se habían conocido antes, pero no sabían que vivían en el mismo vecindario hasta que se toparon en el autobús el día nevado de febrero, unas semanas antes de que el resultado fuera público. Williams describió su prueba al Valiant sobresaltado y prometió enviar su artículo.
“Estaba muy, muy impresionado”, dijo Valiant. “Si obtienes algún resultado matemático que sea lo mejor en 50 años, debes estar haciendo algo bien”.
PSPACE: la frontera final
Con su nueva simulación, Williams había demostrado ser un resultado positivo sobre el poder computacional del espacio: los algoritmos que usan relativamente poco espacio pueden resolver todos los problemas que requieren una cantidad de tiempo algo mayor. Luego, utilizando solo unas pocas líneas de matemáticas, volteó eso y demostró ser un resultado negativo sobre el poder computacional del tiempo: al menos se pueden resolver al menos algunos problemas a menos que use más tiempo que espacio. Ese segundo resultado más estrecho está en línea con lo que esperaban los investigadores. La parte extraña es cómo llegó Williams allí, al demostrar primero un resultado que se aplica a todos los algoritmos, sin importar qué problemas resuelvan.
“Todavía me cuesta creerlo”, dijo Williams. “Parece demasiado bueno para ser verdad”.
Williams usó la técnica de Cook y Mertz para establecer un vínculo más fuerte entre el espacio y el tiempo, el primer progreso en ese problema en 50 años.Fotografía: Katherine Taylor para la revista Quanta
Priturado en términos cualitativos, el segundo resultado de Williams puede parecer la solución desde hace mucho tiempo para el problema P versus PSPACE. La diferencia es una cuestión de escala. P y PSPACE son clases de complejidad muy amplias, mientras que los resultados de Williams funcionan en un nivel más fino. Estableció una brecha cuantitativa entre el poder del espacio y el poder del tiempo, y para demostrar que PSPACE es más grande que P, los investigadores tendrán que hacer que esa brecha sea mucho más amplia.
Ese es un desafío desalentador, similar a excitar una grieta en la acera con una palanca hasta que sea tan ancha como el Gran Cañón. Pero podría ser posible llegar allí utilizando una versión modificada del procedimiento de simulación de Williams que repite el paso clave muchas veces, ahorrando un poco de espacio cada vez. Es como una forma de aumentar repetidamente la longitud de su palanca, hazlo lo suficientemente grande y puedes abrir cualquier cosa. Esa mejora repetida no funciona con la versión actual del algoritmo, pero los investigadores no saben si esa es una limitación fundamental.
“Podría ser un cuello de botella definitivo, o podría ser un cuello de botella de 50 años”, dijo Valiant. “O podría ser algo que tal vez alguien pueda resolver la próxima semana”.
Si el problema se resuelve la próxima semana, Williams se pateará a sí mismo. Antes de escribir el periódico, pasó meses tratando y no extendiendo su resultado. Pero incluso si tal extensión no es posible, Williams confía en que más exploración espacial llevará a un lugar interesante, tal vez progreso en un problema completamente diferente.
“Nunca puedo probar con precisión las cosas que quiero probar”, dijo. “Pero a menudo, lo que pruebo es mucho mejor de lo que quería”.
Nota del editor: Scott Aaronson es miembro de la revista Quanta consejo asesor.
Historia original reimpreso con permiso de Revista cuantauna publicación editorialmente independiente del Fundación Simons cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos de la investigación y las tendencias en matemáticas y las ciencias físicas y de la vida.