For Algorithms, a Little Memory Outweighs a Lot of Time

This article reports on a significant breakthrough in computational complexity theory by MIT computer scientist Ryan Williams. His recent proof, described as “stunning,” demonstrates that a small amount of computer memory (space) can be substantially more powerful than previously understood, potentially being as effective as a large amount of computation time. This marks the first major progress in 50 years on one of computer science’s most famous questions regarding the relationship between time and space resources.

The central theme is the P versus PSPACE problem, which questions whether problems solvable with polynomial amounts of space are inherently harder than those solvable in polynomial time. Williams’ work directly addresses the comparative power of these two fundamental resources.

Key findings and arguments presented include:

• Williams developed a universal mathematical procedure that can transform any algorithm into a new one that uses drastically less memory—specifically, an amount of space roughly proportional to the square root of the original algorithm’s runtime. While these transformed algorithms run slower, the theoretical implication of this space-saving capability is revolutionary.
• This achievement was inspired by recent work (2023) by James Cook and Ian Mertz on the “tree evaluation problem,” which introduced the concept of “catalytic computing” or “squishy pebbles.” This idea challenged the long-held assumption that different pieces of data cannot occupy the same memory space simultaneously, an assumption that had previously limited progress.
• Williams’ result significantly improves upon a 1975 simulation by Hopcroft, Paul, and Valiant, which first established that space is slightly more powerful than time. For decades, their result was thought to be the best possible for universal simulations due to proofs based on the non-overlapping data assumption.

The main conclusions and takeaways are:

• Williams’ proof establishes a much stronger quantitative relationship between computational space and time. It shows that algorithms using relatively little space can solve problems that would otherwise require a considerably larger amount of time, and conversely, implies that some problems cannot be solved unless more time is used than space.
• While this is a major advancement towards understanding the P versus PSPACE problem, it does not fully resolve it. The “gap” demonstrated by Williams’ work would need to be significantly wider to definitively prove that PSPACE is a larger class of problems than P.
• This breakthrough offers a new approach and powerful tools that could potentially be extended to make further progress on P versus PSPACE or other fundamental open problems in theoretical computer science.

Source: https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/