←back to thread

New proof dramatically compresses space needed for computation

(www.scientificamerican.com)
190 points baruchel | 1 comments | 27 Jun 25 13:59 UTC | HN request time: 0.203s | source
Show context
mikewarot ◴[30 Jun 25 10:58 UTC] No.44421746[source]▶
I get that this is an interesting theoretical proof. I'm more interested in the inverse, trading memory for time, to make things faster, even if they take more space. It seems to me the halting problem is almost a proof the inverse of this is impossible.

Memoization is likely the best you can do.

replies(3): >>44423032 #>>44423353 #>>44423922 #
1. burnt-resistor ◴[30 Jun 25 14:38 UTC] No.44423922[source]▶
Dynamic programming and divide-and-conquer with multiple cores on a diagonalized problem space of independent problems (CPU and memory hierarchy) with (hopefully) a final reduce step at the end. Real-world problems are seldom so neat, hence the investment in Infiniband gear.