Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

For algorithms, a little memory outweighs a lot of time

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 144 posts

Re: For algorithms, a little memory outweighs a lot of time

#11

Post by LPisGood »

thatguysaguy wrote: post #5
LPisGood wrote: post #4

I think it is very intuitive that more space beats the pants off of more time. In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.

I think that since many people find it intuitive that P != NP, and PSPACE sits way on top of polynomial hierarchy that it is intuitive even if it’s unproven.

Re: For algorithms, a little memory outweighs a lot of time

#12

Post by Almondsetat »

LPisGood wrote: post #9
qbane wrote: post #7

Earlier quoted context omitted.

But you also spend time on updating cells, so it is not that intuitive.

I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes. More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.

If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.

If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).

Re: For algorithms, a little memory outweighs a lot of time

#13

Post by delusional »

LPisGood wrote: post #9
qbane wrote: post #7

Earlier quoted context omitted.

But you also spend time on updating cells, so it is not that intuitive.

I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes. More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.

This is obviously demonstrably true. A Turing running in O(n) time must halt. The one in O(n) space is free not to.

Re: For algorithms, a little memory outweighs a lot of time

#14

Post by hn_acc1 »

LPisGood wrote: post #4

I think it is very intuitive that more space beats the pants off of more time. In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

My intuition: the value of a cell can represent the result of multiple (many) time units used to compute something. If you cannot store enough intermediate results, you may end up needing to recalculate the same / similar results over and over - at least in some algorithms. So one cell can represent the results of hundreds of time units, and being able to store / load that one value to re-use it later can then replace those same hundreds of time units. In effect, space can be used for "time compression" (like a compressed file) when the time is used to compute similar values multiple times.

If intermediate results are entirely uncorrelated, with no overlap in the work at all, that would not hold - space will not help you. Edit: This kind of problem is very rare. Think of a cache with 0 percent hit rate - almost never happens.

And you can't really do it the other way around (at least not in current computing terms / concepts): you cannot use a single unit of time as a standin / proxy for hundreds of cells, since we don't quite have infinitely-broad SIMD architectures.

Re: For algorithms, a little memory outweighs a lot of time

#15

Post by slt2021 »

hn_acc1 wrote: post #14
LPisGood wrote: post #4

I think it is very intuitive that more space beats the pants off of more time. In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

My intuition: the value of a cell can represent the result of multiple (many) time units used to compute something. If you cannot store enough intermediate results, you may end up needing to recalculate the same / similar results over and over - at least in some algorithms. So one cell can represent the results of hundreds of time units, and being able to store / load that one value to re-use it later can then replac…

I think this theorem applies well for modern LLMs: large language model with pre-computed weights can be used to compute very complex algorithms that approximate human knowledge, that otherwise were impossible or would have required many orders more compute to calculate

Re: For algorithms, a little memory outweighs a lot of time

#17

Post by porphyra »

thatguysaguy wrote: post #5
LPisGood wrote: post #4

I think it is very intuitive that more space beats the pants off of more time. In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.

There's not even a proof that P != EXPTIME haha

EDIT: I am a dumbass and misremembered.

Re: For algorithms, a little memory outweighs a lot of time

#18

Post by [deleted] »

Almondsetat wrote: post #12
LPisGood wrote: post #9

Earlier quoted context omitted.

I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes. More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.

If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage. If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).

[deleted]

Re: For algorithms, a little memory outweighs a lot of time

#19

Post by doc_manhat »

porphyra wrote: post #17
thatguysaguy wrote: post #5

Earlier quoted context omitted.

Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.

There's not even a proof that P != EXPTIME haha EDIT: I am a dumbass and misremembered.

I think there is right? It's been a long time but I seem to remember it following from the time hierarchy theorem

Re: For algorithms, a little memory outweighs a lot of time

#20

Post by thaumasiotes »

delusional wrote: post #13
LPisGood wrote: post #9

Earlier quoted context omitted.

I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes. More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.

This is obviously demonstrably true. A Turing running in O(n) time must halt. The one in O(n) space is free not to.

Almondsetat's proof seems more obvious. Given O(n) time, you can only use O(n) space, so you're comparing "O(n) space, any amount of time" with "O(n) space, O(n) time", and it turns out you get more resources the first way.
Post reply on HN