A computation has two main constraints: the amount of memory a computation requires and how long it takes to do that calculation. If a task requires a certain number of steps, at worst the computer will need to access its memory for each one, meaning it'll require the same number of memory slots.
Prior research within computational complexity has shown that this number can be reduced logarithmically. If a task takes, say, 100 steps, it would only need 50 memory slots, since that is the quotient of X/log X. Ryan Williams, MIT professor of Electrical Engineering and Computer Science and CSAIL principal investigator, just found a way to shrink the memory required further, though — to the tune of about 15 slots for 100 steps in a computation.
The new equation: square root of X log X. Williams' algorithm approaches this as a tree evaluation problem, where calculations are linked in a branching, tree-shaped format. The final result is the "root," which we reach by calculating the "leaves," then its "branches" and further down the tree structure.
When applied to the relationship between time and space, the algorithm revealed a way to dramatically reduce the amount of memory needed for a particular computation. According to Williams, it accomplishes this using mathematical tricks and “magical cancellations” that ultimately provide valid answers.
In a recent article covering this finding, New Scientist journalist Matthew Sparkes likened Williams' approach to the way humans solve complex, multi-step math problems. We don't need to write everything down to make the full calculation, instead relying on limited short-term memory.
The algorithm does not appear to have any immediate practical implications, but "now that we know time-efficient algorithms can be made space-efficient, we can look for trade-offs which are pretty good for both time and space at the same time," says Charles University researcher Ian Mertz.
This story is paraphrased from a recent New Scientist article. Read the full story here.
