An astonishing discovery about the relationship between the amount of memory a computation requires and how long it takes has wowed computer scientists 鈥� although it isn鈥檛 clear if there are any practical applications.
鈥淚t kind of shakes my world view,鈥� says at the Massachusetts Institute of Technology, who made the discovery. 鈥淚鈥檓 still just shocked that it even exists.鈥�
Time and memory space are the two main constraints on what we can compute. Some problems require lots of memory, some lots of time, and many demand a lot of both. Studying these constraints is the domain of computational complexity researchers, who refer to time as the number of steps a computer takes to do a certain task, and space as the number of memory slots the task requires.
Advertisement
Intuitively these values are linked, because if a task requires X steps, in the worst case scenario where the computer needs to access its memory for every step, it will require X memory slots.
But researchers have been able to lower the bar for the amount of memory needed in this worst case scenario. In the 1970s that, in fact, any computation that takes X steps could be done with X/log X of memory. So a program that took 100 time steps, for instance, could always run within 50 memory slots, as log 100 is equal to 2.
鈥淭hat鈥檚 the best that we鈥檝e known until last week,鈥� says at the Illinois Institute of Technology. But then Williams released a surprising that showed that this can be reduced dramatically 鈥� to the square root of X log X. Instead of 100 or 50 memory slots, a 100-step problem could actually be reduced to 15 slots.
鈥淚t was kind of a shocker when Ryan sent this paper around last week, and we were all like, 鈥榳ow鈥�,鈥� says Fortnow.
Williams himself was equally taken aback. 鈥淚t took me months to convince myself that it wasn鈥檛 just obviously false,鈥� he says. 鈥淚t鈥檚 still very difficult for me to wrap my head around it. I can go through all the steps, the proof, and verify every step is correct and that it鈥檚 true. But at the end I鈥檓 still wondering.鈥�
The finding sounds unlikely because it means that computers seem to need only enough space to hold a small part of a problem in memory 鈥� a bit like humans being able to solve a complex, multi-step maths problem without the need to write everything down, relying only on our limited short-term memory.
Williams鈥檚 approach hinges on what is known as the tree evaluation problem. This involves a series of linked calculations in a branching tree-shaped structure, where calculating the final result at the 鈥渞oot鈥� of the tree first involves calculating the 鈥渓eaves鈥�, then 鈥渂ranches鈥�, and so on. in solving the tree evaluation problem have shown that it is possible to do so with an algorithm that is able to re-use computer memory that is already full 鈥� itself a completely unexpected discovery.
To bring this to bear on the question of time and space, Williams created a model that can represent any computational problem, then applied the new tree evaluation algorithm, showing that it could drastically reduce the amount of memory required. It involves mathematical tricks and 鈥渕agical cancellations鈥� that ultimately provide valid answers, he says.
"It feels beyond exciting," says at Charles University in the Czech Republic, one of the researchers that developed the new algorithm. "Definitely a counterintuitive result, although I'd say our tree evaluation algorithms were already pretty counterintuitive."
But while the magnitude of the discovery has shocked computer scientists, it won't necessarily change the way we use computers. The problem is that the finding shows that while you can shrink the amount of memory required to perform a calculation, it won't decrease the time taken. Computer memory is fairly cheap and readily available, so reducing the amount we need isn't a priority.
A discovery that allowed the reverse would mean we could add more memory to computers and speed-up computation as a result - something that would be very helpful as advances in processor speed have begun to slow down - but whether this would be possible is unclear.听"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, and that's useful in a real sense," says Mertz.
Fortnow says he sees no immediate practical implications for the work, but points out that it does provide hope that more surprises in computational complexity could still come and that they might shake-up how we solve hard problems. "You're shocked once, you can be shocked again," he says.
