Nuevo horizonte en la investigación de algoritmos: demuestran que «un poco de memoria puede ser más poderoso que mucho tiempo»

• Una nueva demostración presentada por el teórico de ciencias de la computación de MIT Ryan Williams muestra que la memoria puede ser un recurso computacional más poderoso que el tiempo
• Rompe un estancamiento de 50 años sobre la relación entre complejidad temporal y espacial y propone un método para transformar cualquier algoritmo para que use menos memoria
• La clave de la demostración es generalizar la simulación con ahorro de espacio para reducir el uso de espacio de un algoritmo hasta el nivel de la raíz cuadrada del tiempo
• Con ello, se logró avanzar en la demostración cuantitativa de la diferencia entre las clases PSPACE y P, y también se abre la posibilidad de probar separaciones aún mayores
• Expertos califican este logro como un avance sorprendente y el punto de partida de una nueva exploración, y creen que podría dar pistas para resolver otros problemas difíciles de la informática teórica

---

One Small Step for Space, One Giant Leap for Complexity

Resumen de la nueva demostración de Ryan Williams

• En el verano de 2024, Ryan Williams, de MIT, revisaba su demostración cuando se dio cuenta de que una idea que creía errónea en realidad sí funcionaba
• Propuso un procedimiento general para transformar cualquier algoritmo de modo que pueda ejecutarse con menos memoria
• Eso permitió demostrar que algunos problemas no pueden resolverse dentro de un tiempo limitado

Tiempo y espacio: dos recursos de la computación

• Todo algoritmo usa tiempo y memoria (espacio)
• Hasta ahora, se pensaba que al resolver ciertos problemas el espacio era proporcional al tiempo
• La demostración de Williams establece matemáticamente que el espacio puede ser más poderoso que el tiempo

Origen e historia de la informática teórica

• Juris Hartmanis y Richard Stearns establecieron en los años 60 la definición de complejidad temporal y espacial
• Sentaron las bases para clasificar los problemas en clases de complejidad según los recursos necesarios para resolverlos
• P corresponde a los problemas que pueden resolverse en un tiempo razonable, mientras que PSPACE abarca los que pueden resolverse con una cantidad adecuada de memoria

El primer avance: la técnica de simulación de 1975

• Hopcroft, Paul y Valiant desarrollaron un procedimiento universal de simulación para convertir cualquier algoritmo en otro que usara un poco menos de espacio
• Fue el primer paso para aclarar la relación entre tiempo y espacio, pero después se topó con límites
• Se creía que ya no era posible avanzar más debido a la premisa de que los datos no pueden ocupar el mismo espacio al mismo tiempo

El punto de inflexión: Squishy Pebbles

• En 2010, el pionero de la teoría de la complejidad Stephen Cook y sus colegas idearon el problema de evaluación de árboles - Pebbles and Branching Programs for Tree Evaluation y demostraron que esta tarea era imposible para algoritmos con un presupuesto de espacio inferior a cierto umbral
  • Pero había una grieta en la prueba. Se basaba en la misma suposición de sentido común que Paul y sus colegas habían planteado décadas antes
  • Es decir, que un algoritmo no puede guardar datos nuevos en un espacio que ya está lleno
  • Durante más de 10 años, los teóricos de la complejidad intentaron cerrar esa grieta
• James Cook, hijo de Stephen Cook, e Ian Mertz publicaron en 2023 un algoritmo para el problema de evaluación de árboles que rompe esa premisa: Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Propusieron un nuevo modelo de representación en el que los datos en memoria pueden superponerse físicamente
• Ese enfoque se convirtió en la clave para superar los límites de las simulaciones existentes

El salto decisivo de Williams

• Tras conocer la técnica de Cook-Mertz a partir de una presentación de estudiantes, Williams tuvo la idea de aplicarla a la simulación universal
• La nueva simulación puede reducir los requisitos de espacio de un algoritmo hasta el nivel de la raíz cuadrada del tiempo
• En febrero de 2025 publicó el artículo final en arXiv, donde recibió grandes elogios de la comunidad académica

Qué significa este resultado

• La demostración no prueba directamente que PSPACE > P, pero sí constituye un avance decisivo que abre una ‘brecha’ en esa dirección
• Si en el futuro este procedimiento puede aplicarse repetidamente para crear una separación mayor, podría acercarnos a resolver el problema P vs PSPACE
• Esto podría convertirse en una pista para resolver uno de los problemas más antiguos de la informática

Un cierre con eco

• Williams recordó así el resultado:
  “No logré demostrar exactamente lo que realmente quería demostrar, pero al final lo que demostré fue incluso mejor que lo que quería.”

[nunojay]

....¿eh?

[GN⁺]

Comentarios de Hacker News

• Dicho sin el fuzz, una máquina de Turing multitape que corre en tiempo t puede simularse usando espacio O(sqrt(t log t)) (normalmente tardando más que t) Simulating Time With Square-Root Space
  • Es una lástima que los artículos de Quanta mezclen demasiadas expresiones poéticas o exageradas al hablar de matemáticas y terminen prestándose a malentendidos. En el artículo de Quanta dicen que “ciertas tareas requerían una cantidad de espacio proporcional al tiempo de ejecución”, pero incluso viendo solo la jerarquía de complejidad no sale una intuición general así. No se puede construir toda una intuición general a partir de algo limitado a “algunos algoritmos”.
  • No sé si es por querer ser demasiado amable con el lector, pero me pareció hasta un poco condescendiente que Quanta explicara la clase de complejidad P solo como “todos los problemas que pueden resolverse en un tiempo razonable” sin usar siquiera el término polynomial
• En el “Camel Book”, que recoge la filosofía de Perl, hay una frase así: “Si te falta memoria, puedes comprarla, pero si te falta tiempo, no hay nada que hacer”. Solo digo que le tengo cariño por lo divertido que es el libro
  • También creo que esa frase tiene dos caras. Un programa que necesita más memoria de la que tiene la computadora ni siquiera puede ejecutarse en ese momento, mientras que si solo tarda mucho, de todos modos al menos puede correr; así que el tiempo también termina siendo un recurso importante.
• La victoria de las lookup tables con valores precalculados. Antes pensaba que, si pudiéramos guardar centralmente todos los cálculos hasta el punto de no necesitar procesador, la velocidad de procesamiento podría revolucionarse (aunque en realidad existe el problema aparte de hacer búsquedas rápidas)
  • Recuerdo que cuando empecé a trabajar en sistemas de almacenamiento propuse la idea de precalcular y guardar todos los bloques de 4 KB, y me sorprendió mucho cuando me señalaron que la cantidad de bloques únicos de 4 KB es mayor que el número de átomos en el universo
  • Un algoritmo llamado HashLife hace algo parecido de manera Turing-completa en Conway’s Game of Life. Me parecía fascinante que incluso al tratar estados demasiado complejos y variados, pudiera precalcular estados futuros y saltar hacia adelante.
  • La broma de que no hay problema con la idea de cachear incluso la propia lookup de retrieval
  • En la práctica eso ya se implementa en la distribución de software precompilado a nivel comunidad. La barrera tradicional de tener que renunciar a funciones del lenguaje porque no se puede compilar de forma eficiente también puede superarse con compilación paralela en la nube y cachés globales. Si se compila una sola vez al momento del lanzamiento, todos pueden usarlo.
  • Como continuación de la idea de que “si guardáramos todos los cálculos en un lugar central, parecería que no haría falta procesador”, la propuesta sería memorizar incluso el historial de búsquedas
• Como el estilo de Quanta es tan poético, cuesta entender si esta investigación realmente puede aplicarse a computadoras prácticas o si se trata de un escenario puramente teórico. Me pregunto si significa que la computadora se vuelve más lenta a cambio de usar más memoria.
• Llevo mucho tiempo programando gráficos raster, y el uso de lookup tables se me volvió algo natural. Últimamente desarrollé una herramienta de servidor que mete varias figuras en una BD por adelantado y usa resultados optimizados en cada consulta. Es un patrón que no es complejo y resulta intuitivo. No es algo que haya aprendido especialmente de un profesor del MIT, sino una forma de trabajar que fui adquiriendo en la práctica; por eso me da gusto ver pruebas de que está justificado matemáticamente. También pienso que mucho know-how algorítmico a veces nace de la experiencia de la gente que trabaja en la práctica (ej.: el algoritmo de winding number).
  • Todos los avances que estoy logrando últimamente al optimizar juegos vienen de manejar lookup tables según el contexto. No hace falta que una lookup table sea solo un arreglo estático; datos que cambian un poco con el tiempo también pueden aprovecharse igual. Eso me abrió los ojos a procesar trabajo en la GPU, y es muy eficiente una estructura donde tablas que antes se generaban estáticamente en compilación o en runtime se modifican solo en parte durante la ejecución y luego se pasan a la GPU como si fueran texturas. La frontera de qué llamamos lookup table se vuelve difusa.
• Me resulta intuitivo que el espacio (memoria) puede expresar muchísimos más resultados que el tiempo. En una cinta de longitud n se puede escribir durante tiempo O(n), pero si es una cinta binaria, existen 2^n configuraciones posibles para una longitud n. Si se aprovecha bien el espacio, creo que se obtiene mucha más expresividad que con el tiempo.
  • Mi intuición: en una sola celda pueden guardarse resultados intermedios de cientos de cálculos. Si no se pudieran guardar resultados intermedios y hubiera que recalcular siempre lo mismo, la eficiencia caería mucho. Un escenario con 0% de hit rate en caché es bastante raro, y la mayoría de las veces se puede optimizar aprovechando el espacio. En cambio, es difícil que una sola unidad de tiempo sustituya el espacio de cientos de celdas, y con la arquitectura de cómputo actual un SIMD infinito no es posible.
  • Se da demasiado por sentado el supuesto de acceso aleatorio a memoria O(1), pero en la práctica, mientras más grande se vuelve una computadora, el costo de acceso crece hasta O(n^(1/3)). En un datacenter eso se siente clarísimo. Recuerdo que era otro modelo, no UMA.
  • Como no está demostrado P ≠ PSPACE, es un terreno donde resulta más difícil demostrarlo matemáticamente que seguir la intuición
  • Por otro lado, aunque suena razonable, en problemas difíciles de paralelizar (ej.: alternating machine PTIME=PSPACE) el espacio quizá no dé una ventaja tan grande. En el artículo el salto de t/log t a sqrt(t log t) es revolucionario, pero debe haber límites sustanciales que ni siquiera la paralelización infinita puede superar.
  • En la práctica depende de la naturaleza del trabajo. Cuando acceder al almacenamiento es mucho más lento que hacer una asignación, a veces recalcular resulta más rápido.
• La “relación inversa” entre tiempo y espacio puede explicarse como el fenómeno de que, al restringir uno de los dos recursos, no siempre se puede obtener el óptimo del otro. Por ejemplo, en algoritmos de ordenamiento, si existen tres restricciones de tiempo/espacio/estabilidad, al exigir además estabilidad puede empeorar la eficiencia en tiempo o espacio. Hasta ahora no existe un ordenamiento estable que sea tan rápido y use tan poca memoria como los no estables.
• Personalmente me gusta el estilo de los artículos de Quanta Magazine. Amplía la perspectiva no solo a científicos de la computación, sino también a personas comunes interesadas en áreas relacionadas. Esa vista panorámica y esa forma cercana de explicar sirven como punto de partida para nuevas perspectivas e ideas.
• Comparto enlaces a una charla y un paper de Ryan Williams
• Si una máquina de Turing de una sola cinta recibe como entrada un número binario N y quiere escribir N veces el valor 1 a la derecha de la cinta, parecería necesitar espacio N en tiempo N. Entonces me pregunto cómo podría simularse con menos espacio que N. Dadas las características estructurales de una máquina de Turing, que no puede saltar a una posición arbitraria de la cinta, también me pregunto qué relación real tiene esto con una computadora de verdad.
  • Las máquinas de Turing multitape son muchísimo más rápidas que las de una sola cinta, y el “espacio” del que se habla aquí es espacio de trabajo temporal, excluyendo entrada/salida.
  • El paper se enfoca principalmente en problemas de decisión, es decir, situaciones donde la salida solo necesita 1 bit. Si la salida fuera de N bits, en la práctica eso equivale a encadenar N problemas de decisión.