'For Algorithms, a Little Memory Outweighs a Lot of Time' (quantamagazine.org)
- Reference: 0177951195
- News link: https://developers.slashdot.org/story/25/06/07/0714256/for-algorithms-a-little-memory-outweighs-a-lot-of-time
- Source link: https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521
"In February, he finally [2]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 [3]mspohr for sharing the article.
[1] https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521
[2] https://arxiv.org/abs/2502.17779
[3] https://www.slashdot.org/~mspohr
Look here (Score:2)
The link to the research is in the second link in th OP.
Is this related to Squeeze Space into Time? (Score:2)
Sorry I just woke up can't think properly. But just saw this yesterday until the end before bed. [1]https://www.youtube.com/watch?... [youtube.com]
[1] https://www.youtube.com/watch?v=8JuWdXrCmWg
Looks like a theorerical result (Score:2)
No implication for doing actual computations.
I haven't read the paper (Score:2)
But it seems to me you could turn every variable reference into a function to do everything needed to compute that value instead. Inefficient as fuck, but it would remove all space requirements.
Re: I haven't read the paper (Score:2)
That's just kicking the can down the road. Besides, every function needs memory to store its definition, so you've saved nothing.
Fallacy (Score:1)
"Proving a suspected murderer guilty by establishing an ironclad alibi for everyone else on the planet"
I'll see your Sherlock Holmes fallacy and raise you a Reverse Burden of Proof fallacy.
There is no CS in the article (Score:2)
If you studied computer science and didn't forget all of it, the article is a tease.
> Algorithms that use relatively little space can solve all problems that require a somewhat larger amount of time. Then, using just a few lines of math, he flipped that around and proved a negative result about the computational power of time: At least a few problems can’t be solved unless you use more time than space
This is gibberish. I'm pretty sure every phrase that says "little space", "more time", etc., should be replaced by the name of a complexity class or a space complexity class.
Though perhaps it's too hard to really explain it in the way that P and NP are usually explained (with a simple example).
Re: There is no CS in the article (Score:2)
The link works fine, so you likely don't know how to operate the link, as you freely admitted.
Re: There is no CS in the article (Score:2)
I can, can't you?
[1]https://arxiv.org/pdf/2502.177... [arxiv.org]
[1] https://arxiv.org/pdf/2502.17779
Re: There is no CS in the article (Score:1)
Welcome to the world of disinformation. It's pretty obvious that this is a farce and a hoax.
Re: (Score:2)
> If you studied computer science and didn't forget all of it, the article is a tease.
Quanta's focus is to help educate the person who does not have a CS degree. If you took classes with Hartmanis or Hopcroft, you are not the expected reader of this article.
Re: (Score:2)
This article explains the algorithm and is targeted toward the non-CS audience.
It may be difficult for some people to understand but they do boil it down to simple terms.
Those who are interested can read the paper at:
[1]https://arxiv.org/pdf/2502.177... [arxiv.org]
[1] https://arxiv.org/pdf/2502.17779