alt Hacker News> Ryan Williams found that any problem solvable in time t needs only about sqrt(t) bits of memory
At least or at most or on average?
> Ryan Williams found that any problem solvable in time t needs only about sqrt(t) bits of memory
At least or at most or on average?
I've skimmed the result couple of weeks ago, and if I remember it states that there from all machines which takes t time to accomplish something there is one such that sqrt(t) memory is used. so it's at most but not on avg nor amorotized[not sure if et even make sense it the space where the problem lies] (you take the least memory hungry machine)