Feed: Slashdot
Feed Link: https://slashdot.org/
---

Title: 'For Algorithms, a Little Memory Outweighs a Lot of Time'

Link: https://developers.slashdot.org/story/25/06/0...

MIT comp-sci professor Ryan Williams suspected that a small amount of memory
"would be as helpful as a lot of time in all conceivable computations..."
writes Quanta magazine. "In February, he finally posted his proof online, to
widespread acclaim..." Every algorithm takes some time to run, and requires
some space to store data while it's running. Until now, the only known
algorithms for accomplishing certain tasks required an amount of space
roughly proportional to their runtime, and researchers had long assumed
there's no way to do better. Williams' proof established a mathematical
procedure for transforming any algorithm - no matter what it does - into a
form that uses much less space. What's more, this result - a statement about
what you can compute given a certain amount of space - also implies a second
result, about what you cannot compute in a certain amount of time. This
second result isn't surprising in itself: Researchers expected it to be true,
but they had no idea how to prove it. Williams' solution, based on his
sweeping first result, feels almost cartoonishly excessive, akin to proving a
suspected murderer guilty by establishing an ironclad alibi for everyone else
on the planet. It could also offer a new way to attack one of the oldest open
problems in computer science. "It's a pretty stunning result, and a massive
advance," said Paul Beame, a computer scientist at the University of
Washington. Thanks to long-time Slashdot reader mspohr for sharing the
article.

Read more of this story at Slashdot.

---
VRSS v2.1.180528