[HN Gopher] You need much less memory than time
       ___________________________________________________________________
        
       You need much less memory than time
        
       Author : jonbaer
       Score  : 29 points
       Date   : 2025-06-07 21:38 UTC (1 hours ago)
        
 (HTM) web link (blog.computationalcomplexity.org)
 (TXT) w3m dump (blog.computationalcomplexity.org)
        
       | 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 ?
        
       | 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.
        
       ___________________________________________________________________
       (page generated 2025-06-07 23:00 UTC)