For Algorithms, Memory Is a Far More Powerful Resource Than Time
1 min read
Summary
In February 2025, Ryan Williams proved a long-standing conjecture in computer science that space can be as powerful as time for computing.
Williams, a theoretical computer scientist at MIT, showed that a small amount of memory can be as helpful as a lot of time for all conceivable computations.
It had been believed that efficiency in using space and time in computing have similar capabilities, but Williams’ proof showed that a small amount of memory would be as helpful as a lot of time.
The finding also implies that at least a few problems can’t be solved in a certain time, which researchers had not known.
Williams found the result after he proved a different conjecture about space and computer memory.
