More Time Less Space: An Insight Into the Future of Theoretical Computer Science
Computation and Complexity | Jake Anderson
Background
In the year 2000, mathematics' brightest minds came together to list what they deemed as the seven greatest unsolved problems to date. The organisers promised researchers that they would commit one million dollars for solving any of the problems. One way of winning the money and having eternal scientific fame is to solve the P vs NP problem, which has eluded mathematicians and computer scientists for over 50 years [1].
At its core, the question asks whether every problem whose solution can be quickly verified by a computer could also be solved just as quickly from scratch. For example, a problem in NP would be how many colours you need to colour a map so that no two neighbouring regions have the same colour. Finding the colouring can be surprisingly difficult, but checking a proposed solution is easy. On the other hand, problems for which the task itself is easy to solve belong to P [1], [2].
The impact of showing P = NP would be monumental: modern-day cryptography relies on the very idea of problems being hard to solve (for privacy) and easy to verify (for the receiver), meaning it would be possible to easily break complex encryption schemes [1]. With all of this in mind, it should be no surprise that some of the brightest minds in theoretical computer science have attempted to write their name in history, yet little progress had been made up until recently.
The Man With a Plan
Ryan Williams, a professor at MIT, is no stranger to taking on the hardest problems in theoretical computer science. As a complexity theorist, his job isn't to empirically compare algorithm runtime, but to map out the absolute mathematical limits of computational rules that remain true no matter how powerful future computers become.
In computer science, two resources matter above all else: time (how many operations a program takes) and space (how much memory it needs). While time strictly moves forward, memory, on the other hand, can be erased and reused. Because of this, theorists have long suspected that memory is inherently more versatile than time [2], [3].
For decades, the assumption was that a program running for t steps might require up to t slots of memory for every moment in time. The first major breakthrough came in 1977, when researchers John Hopcroft, Wolfgang Paul, and Leslie Valiant proved we could do better. By modelling a program's execution as a strategy game involving moving markers on a grid (a technique called graph pebbling), they proved that any t-step computation could be squeezed into slightly less space: roughly t/log(t) memory [4].
While the Hopcroft–Paul–Valiant theorem was a milestone by proving that time and space behave differently, it still left a huge gap between what scientists believed was possible and what they could mathematically prove [3], [4].
That changed when Williams achieved a monumental leap forward. Building on these space-saving concepts, he proved that algorithms can be simulated using space proportional to only the square root of their running time (√t). To put that in perspective, a computation running for a million steps doesn't need a million memory slots; it can be executed using just 1,000. By showing how drastically memory can be compressed, Williams redefined our understanding of how time and space interact at the fundamental level [3], [5], [6].
Figure 1: Demonstration of the graph pebbling game modelling memory allocation.
The Proof: A Story of Unlikely Connections
No scientific breakthrough happens in isolation, and Williams' proof relied on a crucial key step provided by fellow complexity theorists Ian Mertz (who recently delivered a seminar on this work at the University of Auckland) and James Cook [6], [7].
For over a decade, researchers had been studying a benchmark challenge known as the Tree Evaluation Problem. The setup resembles a tournament bracket: input data starts at the bottom "leaves", and each internal node applies a mathematical rule to combine its children's values, bubbling up to a single output at the root. The standard way to evaluate the tree requires holding many intermediate results in memory at once. For years, scientists conjectured that evaluating such trees strictly required a large amount of memory, hoping this hardness would help distinguish between time and space bounds [7], [8].
That assumption was shattered when Mertz and Cook published a revolutionary algorithm. Drawing inspiration from catalytic computing, a technique where an algorithm "borrows" occupied memory, uses it as temporary space, and meticulously restores it to its exact original state before finishing, they proved that trees could be evaluated using far less space than previously thought possible [7].
While many in the field initially assumed Mertz and Cook's result meant tree evaluation was "too easy" to be useful for proving memory limits, Williams saw its true potential. He proved that any computer program running for t steps can be restructured and mapped onto a tree evaluation instance. By plugging Mertz and Cook's efficient algorithm into this new framework, Williams achieved his historic ≈ √t space simulation [6], [7].
Figure 2: Visualisation of Tree Evaluation.
Why Care?
So, how does compressing memory bring us any closer to solving the million-dollar P vs NP problem? The secret lies in how complexity classes are nested.
Computer scientists know that these fundamental classes form a natural chain:
… ⊆ L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE ⊆ …
Here, PSPACE represents the set of all problems solvable using a reasonable (polynomial) amount of memory. Notice that NP is trapped directly in the middle. This sandwiching creates a vital backdoor: if researchers can prove whether polynomial time (P) is equal to or different from polynomial space (PSPACE), they automatically shed light on NP. In fact, if P = PSPACE, then P = NP would follow automatically [2].
For half a century, proving a concrete, mathematical separation between time and space seemed completely out of reach. But Williams' ≈ √t simulation provided the key. By showing that a tiny amount of memory can simulate a huge amount of execution time, Williams proved a groundbreaking corollary: there are explicit problems solvable using a small, linear amount of memory (O(n) space) that strictly require nearly quadratic running time (n² time) to complete [3], [6].
This marked the first time in history that computer scientists established a general polynomial gap between time and memory on standard computational models. While it doesn't resolve P vs PSPACE entirely (because the square root of a polynomial is still a polynomial) it proves that space is fundamentally more powerful than time.
A Step Closer to the Prize
While Ryan Williams' breakthrough does not claim the million-dollar Millennium Prize overnight, it fundamentally reshapes our understanding of the mathematical universe. For half a century, complexity theorists felt stuck against an invisible wall, unable to prove even basic mathematical separations between the time an algorithm takes to run and the memory it consumes.
By taking Ian Mertz and James Cook's counterintuitive result on tree evaluation and pairing it with space-efficient simulation techniques, Williams demonstrated that progress on the deepest questions in theoretical computer science often comes from unexpected directions. We now know with mathematical certainty that space is fundamentally more powerful than time.
The complete resolution of P vs NP remains one of humanity's greatest unsolved intellectual challenges. Yet results like these prove that the wall separating time and space is far from unbreakable. With every new theoretical bridge built between seemingly unrelated problems, researchers are inching closer to mapping the true limits of computation and perhaps, one day, claiming eternal scientific fame.
[1] S. Cook, “The P versus NP problem,” in The Millennium Prize Problems, J. Carlson, A. Jaffe, and A. Wiles, Eds., Cambridge, MA, USA: Clay Mathematics Institute/American Mathematical Society, 2006, pp. 106–114.
[2] S. Arora and B. Barak, Computational Complexity: A Modern Approach. Cambridge, UK: Cambridge University Press, 2009, doi: 10.1017/CBO9780511804090.
[3] B. Brubaker. “For Algorithms, a Little Memory Outweighs a Lot of Time.” Quanta Magazine. Accessed: Aug. 24, 2026. [Online]. Available: https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/.
[4] J. Hopcroft, W. Paul, and L. Valiant, “On Time Versus Space,” J. ACM, vol. 24, no. 2, pp. 332–337, Apr. 1977, doi: 10.1145/322003.322015.
[5] R. Williams, Institute for Advanced Study, Princeton, NJ, USA. Simulating Time With Square-Root Space (And With Details). (Sept. 24, 2025). Accessed: Aug. 24, 2026. [Online Video]. Available: https://youtu.be/ThLvLewiRnQ.
[6] R. Williams, “Simulating Time with Square-Root Space,” in STOC 2025: Proc. 57th Annu. ACM Symp. Theory Comput. (STOC), 2025, pp. 13–23, doi: 10.1145/3717823.3718225.
[7] J. Cook and I. Mertz, “Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛),” in STOC 2024: Proc. 56th Annu. ACM Symp. Theory Comput., 2024, pp. 1268–1278, doi: 10.1145/3618260.3649664.
[8] S. Cook, P. McKenzie, D. Wehr, M. Braverman, and R. Santhanam, “Pebbles and Branching Programs for Tree Evaluation,” ACM Trans. Comput. Theory, vol. 3, no. 2, pp. 4:1–43, Jan. 2012, doi: 10.1145/2077336.2077337.
Jake Anderson- PhD Computer Science (Complexity Theory)
Jake is a British PhD candidate working in theoretical computer science with a focus on proof complexity. When not found around a whiteboard he can be seen riding a bike or running.