←back to thread

190 points baruchel | 1 comments | | HN request time: 0.314s | source
Show context
zerof1l ◴[] No.44421424[source]
Here's the gist:

For nearly 50 years theorists believed that if solving a problem takes t steps, it should also need roughly t bits of memory: 100 steps - 100bits. To be exact t/log(t).

Ryan Williams found that any problem solvable in time t needs only about sqrt(t) bits of memory: a 100-step computation could be compressed and solved with something on the order of 10 bits.

replies(7): >>44422352 #>>44422406 #>>44422458 #>>44422855 #>>44423750 #>>44424342 #>>44425220 #
taneq ◴[] No.44422458[source]
Huh? What did any of those theorists think about the phrase "time/space tradeoff"?
replies(2): >>44422643 #>>44422948 #
mhuffman ◴[] No.44422643[source]
They were likely the ones that invented the phrase.
replies(2): >>44423188 #>>44423268 #
taneq ◴[] No.44423188[source]
I'm not convinced of that if they thought that s=O(t/log(t)) where s=space (bytes or similar) and t=time (clocks, steps, etc.) I dunno about theoretical limits but in practice, there's at least 1-2 orders of magnitude to be exchanged between space and processing time.
replies(1): >>44424669 #
1. eru ◴[] No.44424669[source]
That's in practice for practical problems. But they were interested in the worst cases.