[HN Gopher] You need much less memory than time
___________________________________________________________________
You need much less memory than time
https://arxiv.org/abs/2502.17779
Author : jonbaer
Score : 115 points
Date : 2025-06-07 21:38 UTC (1 days ago)
(HTM) web link (blog.computationalcomplexity.org)
(TXT) w3m dump (blog.computationalcomplexity.org)
| slicktux wrote:
| It's nice to see what a little bitwise manipulation can do(XOR)!
| Low level programming is always fun!
| dang wrote:
| Related. Others?
|
| _For algorithms, a little memory outweighs a lot of time_ -
| https://news.ycombinator.com/item?id=44055347 - May 2025 (139
| comments)
| krackers wrote:
| Dupe of today's https://news.ycombinator.com/item?id=44212861 ?
| dang wrote:
| It looks like that posted just a little later (by the same
| submitter) so I've put a copy of that link at the top.
| laex wrote:
| See Kelsey Houston-Edwards's exceptional breakdown of Williams'
| paper, & Scott Aranson's thoughts on the topic.
|
| [1] https://www.youtube.com/watch?v=8JuWdXrCmWg
|
| [2] https://scottaaronson.blog/?p=8680
| npinsker wrote:
| I think the summary at the beginning of your first video is
| misleading; it's not a way to "trade space for time", at least
| not in an arbitrary program. The real statement is a bit odder
| to wrap one's head around -- "every problem solvable in t time
| on a multitape Turing machine is also solvable in close to [?]t
| space".
|
| For a Turing machine that already solves a problem in n time
| and [?]n space (in other words, a lot of them!), it doesn't say
| anything.
| LegionMammal978 wrote:
| When you convert a generic Turing machine into a Tree
| Evaluation instance, you end up with square-root space with
| respect to the original runtime _t_ , but the new runtime
| will be far, far slower. IME, with these types of circuit
| reductions, the runtime typically becomes exponential in the
| space required, which is just about 'as long as possible'.
|
| If we're being pedantic, it's trading time for the space
| _guarantee_.
| throwaway81523 wrote:
| From Februray 2025 fwiw. Same result there have been multiple
| articles here about. I wonder how it would work for Haskell
| programs (no mutable memory).
| HappMacDonald wrote:
| I'd view "no mutable memory" as misleading, because immutable
| languages can still create a new variable and forget an old one
| which has the same memory footprint as mutating one variable.
|
| Obvious example: the flickering stack frame of tail call
| elimination.
| curtisf wrote:
| Haskell has genuine mutable memory, through State and IO.
|
| But even without it, you can emulate mutation in a pure
| language by threading a "heap" parameter through everything.
|
| There's only at most a log factor of extra space and time
| required in most computing models to "update" a persistent map
| (though I'm not sure the best way to encode persistent maps
| directly in Turing machine tapes, which is the model this
| result is specifically about)
| wewewedxfgdf wrote:
| What are the practical implications and use cases of this?
|
| Is it something like some sort of reverse compiler which creates
| super efficient code by analyzing the inverse flow of code or
| something?
___________________________________________________________________
(page generated 2025-06-08 23:02 UTC)