'For Algorithms, a Little Memory Outweighs a Lot of Time' (quantamagazine.org) 37
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.
"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.
There is no CS in the article (Score:3)
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)
Re: There is no CS in the article (Score:5, Informative)
I can, can't you?
https://arxiv.org/pdf/2502.177... [arxiv.org]
Re: There is no CS in the article (Score:1)
Re: (Score:2)
So, the paper they are describing, which has been discussed for months in the industry, and published as linked: https://arxiv.org/pdf/2502.177... [arxiv.org] -- all 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:There is no CS in the article (Score:4, Informative)
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:
https://arxiv.org/pdf/2502.177... [arxiv.org]
Re: (Score:3)
Exactly. Usually when you analyze algorithms you care about runtime - because that affects how fast it runs. But there are other considerations as well - including space - some algorithms may run very fast, but consume a lot of memory, while other algorithms to do the same thing can have a longer runtime but use less memory. What you choose depends on your situation.
And there's also the case where simple is better - even bubble sort is fast if your n is small. If you have a well constrained list of items th
Re: (Score:1)
Re: (Score:3)
Look here (Score:2)
Is this related to Squeeze Space into Time? (Score:3)
Looks like a theorerical result (Score:2)
No implication for doing actual computations.
Re: (Score:1)
But it will generate generations of buzzwords for salespeople to dupe clueless managers with. It's a sales efficiency algorithm. It's like greatly improving on a traveling salesperson algorithm, but by using deeper bullshit instead of better routes.
Re: (Score:1)
Indeed. It will convince the same morons that think AI is sentient, we will be going to Mars next year but vaccines do not work. There was no better time in history to learn about the limitations of the average person than now. Lack of educaton or access to information is not a factro anymore. It is all 100% genuine stupid.
Re: (Score:1)
> It will convince the same morons that think AI is sentient
Many human morons are not sentient, they just echo their cult leader.
I haven't read the paper (Score:2)
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.
Re: (Score:2)
I did not read the paper. Only some comments based on the video: https://www.youtube.com/watch?... [youtube.com]
If I understand it correctly; using references to recompute everything in a data dependency manner to save as much space as possible would lead only to space reduction of O(t*log(t)) when compared to space unconstrained algorithm (i.e. an algorithm which uses about as much space as time). This is the old result. They also shift "temporary" variables typically needed during an computation into the computation i
replace O(t*log(t)) with O(t/log(t)) in parent (Score:2)
Re: (Score:2)
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.
The opposite is more interesting (Score:2)
There are countless examples where more memory saves a lot of computing time. For instance precomputing huge tables of complex functions aided by interpolation allows to spare recomputing these frequently used functions.
exponential space (Score:2)
Every NP complete problem is solvable in P time using exponential space, shut up
Re: (Score:2)
Re: (Score:3)
You'll need to have a NDTM 2.0 to run Windows 12 anyway. So, upgrade now.
ELI5 (Score:2)
Re: (Score:2)
The proof is for multitape Turing machines. You can't ELI5 that stuff.
Re: (Score:3)
The proof is for multitape Turing machines. You can't ELI5 that stuff.
You can, you just need an infinite number of five year-olds.
Re: (Score:2)
Good luck finding an infinite number of tape recorders. The five year olds today have an infinite number of spotify subscriptions.
Re: (Score:2)
Re: (Score:1)
Important, but uses slowness of Turing Machines (Score:3)
YouTube lecture on this by the discoverer, Ryan Williams [youtube.com]
Ryan Willaims's paper, "Simulating Time With Square-Root Space [arxiv.org]
This appears to be based partly but largely on Tree Evaluation is in Space O(log n * log log n)" by James Cook and Ian Mertz (2023 colloqium [weizmann.ac.il], STOC 2024 conference [acm.org]).
I'm just a programmer who has spent an hour or so looking at this, so please take the rest of this post with a grain of salt.
I get the impression that Professor Williams's result so far, already a tool for making progress about which computational complexity classes are the same and different, has the limitation of relying on how slow Turing machines are at accessing memory, based on the mention at 18min:50sec into that YouTube Video of how the space savings degrades for a Turing machine with tapes of more than one dimension. If I understand correctly, for such Turing machines, an algorithm with running time bounded above by time T(n) for any input of length n, the space used by this potentially much slower space-saving simulation is bounded by O( ( T(n) + log T(n) ) ** ( 1 - (1/(D+1))) ). I'm using "**" as exponentiation, so the exponent means square root (that is, exponent 0.5) for a one dimensional (linear) tape, two thirds power (exponent 0.66...) for a tape that is a two dimensional surface, 0.75th power for a three dimensional tape, and, so far, no known savings for a tree shaped tape, although I suppose that that three dimensional limit does ultimately apply to real world data storage systems.