For Algorithms, a Little Memory Outweighs a Lot of Time
1 min read
Summary
Fifty years ago, computer scientists proved that certain kinds of computations require much more space than time — and that’s been the status quo ever since.
Last February Ryan Williams of the Massachusetts Institute of Technology proved the opposite, establishing a general relationship between an algorithm’s time and space budgets.
One consequence of his work is that certain computations may demand more time than space.
This could also offer a new angle for tackling one of the oldest open problems in computer science: the distinction between problems that can be solved in a reasonable amount of time and those that cannot.
“It’s a pretty stunning result, and a massive advance,” says Paul Beame, a computer scientist at the University of Washington. “It’s a little bit less of a surprise that it’s Ryan doing this.
