Esas son limitaciones bastante estrictas, por lo que no period obvio que la memoria adicional podría resultar útil. Pero para su sorpresa, Buhrman y Cleve demostraron que si modifica los bits de la manera correcta, realmente puede obtener un empuje computacional adicional de una memoria completa.
“Eso fue una sorpresa para todos”, dijo Loff, quien period un estudiante de posgrado en el grupo de Buhrman en ese momento, trabajando en la pregunta de memoria con su compañero de estudios. Florian Speelman. El equipo pronto extendió el resultado a una clase de problemas aún más grande, y publicó sus resultados combinados en 2014.
Llamaron a la nueva computación catalítica de marco, tomando prestado un término de la química. “Sin el catalizador, la reacción no habría procedido”, dijo Raghunath Tewariun teórico de la complejidad del Instituto Indio de Tecnología, Kanpur. “Pero el catalizador en sí no cambia”.
No muy lejos del árbol
Una pequeña banda de investigadores continuó desarrollando la computación catalítica aún más, pero nadie trató de aplicarlo al problema de evaluación de árboles que inicialmente había inspirado la búsqueda de Koucký. Para ese problema, la pregunta abierta restante period si se podía usar una pequeña cantidad de memoria para el almacenamiento y el cálculo simultáneamente. Pero las técnicas de la computación catalítica se basaban en la memoria adicional, siendo muy grande. Encoge esa memoria y las técnicas ya no funcionan.
Aún así, un joven investigador no pudo evitar preguntarse si había una manera de adaptar esas técnicas para reutilizar la memoria en un algoritmo de evaluación de árboles. Su nombre period James Cooky para él, el problema de evaluación de los árboles period private: Stephen Prepare dinner, el legendario teórico de la complejidad que lo inventó, es su padre. James incluso había trabajado en ello en la escuela de posgrado, aunque se centró principalmente en sujetos completamente no relacionados. Cuando encontró el documento de computación catalítica unique en 2014, James estaba a punto de graduarse y dejar la academia para la ingeniería de software program. Pero incluso cuando se instaló en su nuevo trabajo, seguía pensando en la informática catalítica.
“Tuve que entenderlo y ver qué se podía hacer”, dijo.
Durante años, James Prepare dinner jugó con un enfoque catalítico para el problema de evaluación del árbol en su tiempo libre. Dio una charla sobre su progreso en un simposio de 2019 en honor a su padre trabajo innovador en teoría de la complejidad. Después de la charla, se le acercó un estudiante graduado llamado Ian Mertzquien se había enamorado de la computación catalítica cinco años antes después de enterarse de ello como una joven estudiante impresionable.
“Period como un escenario de impresión de pájaros para bebés”, dijo Mertz.
Fotografía: Revista Stefan Grosser/Quanta
Prepare dinner y Mertz unieron fuerzas, y sus esfuerzos pronto valieron la pena. En 2020, idearon un algoritmo Eso resolvió el problema de evaluación del árbol con menos memoria que un mínimo necesario conjeturado por el anciano Prepare dinner y McKenzie, aunque estaba apenas por debajo de ese umbral. Aún así, eso fue suficiente para cobrar la apuesta de $ 100; Convenientemente para los cocineros, la mitad se quedó en la familia.
Pero todavía había trabajo por hacer. Los investigadores comenzaron a estudiar la evaluación de los árboles porque parecía que finalmente podría proporcionar un ejemplo de un problema en P que no está en L, en otras palabras, un problema relativamente fácil que no se puede resolver usando muy poca memoria. El nuevo método de Prepare dinner y Mertz usó menos memoria que cualquier otro algoritmo de evaluación de árboles, pero aún usó significativamente más que cualquier algoritmo para un problema en L. La evaluación del árbol estaba inactiva, pero no fuera.
En 2023, Prepare dinner y Mertz salieron con un algoritmo mejorado Eso usaba mucha menos memoria, casi más que el máximo permitido para los problemas en L. Muchos investigadores ahora sospechan que la evaluación de los árboles está en L después de todo, y que una prueba es solo cuestión de tiempo. Los teóricos de la complejidad pueden necesitar un enfoque diferente al problema P versus L.
Mientras tanto, los resultados de Prepare dinner y Mertz han galvanizado el interés en la computación catalítica, con nuevos trabajos explorando conexiones con la aleatoriedad y los efectos de permitir un pocos errores al restablecer la memoria completa a su estado unique.
“No hemos terminado de explorar lo que podemos hacer con estas nuevas técnicas”, dijo McKenzie. “Podemos esperar aún más sorpresas”.
Historia original reimpreso con permiso de Revista cuanta, una 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.
