Time and memory (also known as space) are the most fundamental resources in computation – all algorithms require space to store data and time to run. In 2024, Ryan Williams, theoretical computer scientist at the Massachusetts Institute of Technology, made an extraordinary discovery about the nature of memory and time in computing. His findings suggested that memory was significantly more powerful than computer scientists believed: a small amount of memory would – in all perceivable computations – be as helpful as a lot of time.
Transforming Algorithms
Algorithms are procedures used to perform computations or solve problems. They act as a precise set of instructions to conduct specific actions in either software- or hardware-based systems. Algorithms can be expressed as programming languages, natural languages, flowcharts, control tables and pseudocode. Williams’ discovery established a mathematical procedure to transform any algorithm into a form using much less space. Prior to this, the only known algorithms to accomplish certain tasks needed space approximately proportionate to their runtime, with researchers assuming there was no way to improve this. Wiliams’ proof also helped clarify what can and cannot be computed within a certain amount of time.
The Limited Space Problem
Ryan Williams’ new result in memory and time in computing sprang from work on a different question: what problems are solvable with very limited space? In 2010, complexity theorist Stephen Cook and collaborators invented the tree evaluation problem. The team proved that no algorithm with a space budget below a certain threshold would be able to solve the task…but a loophole existed.
As those interested in this subject – such as Jonathan De Vita – understand, this proof relied on the assumption that it’s impossible for algorithms to store data in a space already full. For more than a decade, complexity theorists attempted to close this loophole. In 2023, Ian Mertz and James Cook (Stephen’s son) came up with an algorithm that used much less space than anyone thought possible to solve the tree evaluation problem.
Despite this breakthrough, it was unclear whether the algorithm had any application beyond the specific problem itself – until Ryan Williams made a breakthrough. In 2024, he was inspired to take a closer look at Cook and Mertz’s paper following a group of students’ presentation on the subject. Williams quickly realised that the solution was a general-purpose tool to reduce space usage. For more information on how algorithms work, take a look at the embedded PDF.