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

71–80 of 144 posts

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

#71

Post by IsTom »

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.

One one hand yes, on the other there might be some problems that are inherently difficult to parallelize (alternating machine PTIME is the same as deterministic PSPACE) where space doesn't buy you much. The jump from paper from t/log t to sqrt(t log t) is huge, but it still might be that unbounded parallelism doesn't buy you much more.

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

#72

Post by qbane »

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.

A time-bounded TM is also space bounded, because you need time to write to that many cells. But the other way is not.

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

#73

Post by woolion »

It's unfortunate that Quanta links are so popular, when they include so much pseudo-poetic fluff around the mathematics. Below there's an entire thread to dismiss a misconception introduced by the quanta article.

"I think it is very intuitive that more space beats the pants off of more time." (poster is absolutely right) The The article say "Until now, the only known algorithms for accomplishing certain tasks required an amount of space roughly proportional to their runtime, and researchers had long assumed there’s no way to do better.", which is interpreted as that there's a proportional relation between time and space. However, a quick look at the complexity hierarchy would never suggest such a thing. Reading more carefully, it says "known algorithms" for "certain tasks", but then where do you get a general intuition from such a particular statement?

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

#74

Post by iNic »

IvanK_net wrote: post #24

I am confused. If a single-tape turing machine receives a digit N in binary, and is supposed to write N ones on the tape, on the right side of the digit N, it performs N steps. If you expect N ones at the output, how can this machine be simulated in the space smaller than N? This machine must decrement the digit N at the beginning of the tape, and move to the end of the tape to write "1", so it runs in time O(N^2), n…

This paper looks exclusively at decision problems, i.e. problems where the output is a single bit.

EDIT: This makes sense because if you look at all problems with N outputs then that is just the same as "gluing together" N different decision problems (+ some epsilon of overhead)

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

#75

Post by immibis »

xlii wrote: post #68

From the „Camel Book”, one of my favorite programming books (not because it was enlightening, but because it was entertaining); on the Perl philosophy: “If you’re running out of memory, you can buy more. But if you’re running out of time, you’re screwed.”

This can work both ways. If the program needs more memory than the computer has, it can't run until you buy more. But if it takes twice as long, at least it runs at all.

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

#76

Post by immibis »

frollogaston wrote: post #54
manwe150 wrote: post #48

Earlier quoted context omitted.

That example would be two dimensions still in the limit computation, since you can keep building outwards (add buildings) but not scale upwards (add floors)

You can add floors though. Some datacenters are 8 stories with cross-floor network fabrics.

When you get to, say, 100000 stories, you can't build more stories. At this point your computer costs more than the Earth's GDP for a century, so talking about theoretical scaling laws is irrelevant. Eventually you run out of the sun's power output so you build a Dyson sphere and eventually use all of that power, anyway.

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

#77

Post by walterbell »

EGreg wrote: post #41
whatever1 wrote: post #16

Lookup tables with precalculated things for the win! In fact I don’t think we would need processors anymore if we were centrally storing all of the operations ever done in our processors. Now fast retrieval is another problem for another thread.

You’re not wrong Using an LLM and caching eg FAQs can save a lot of token credits AI is basically solving a search problem and the models are just approximations of the data - like linear regression or fourier transforms. The training is basically your precalculation. The key is that it precalculates a model with billions of parameters, not overfitting with an exact random set of answers hehe

> Using an LLM and caching eg FAQs can save a lot of token credits

Do LLM providers use caches for FAQs, without changing the number of tokens billed to customer?

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

#78

Post by plastic3169 »

jodrellblank wrote: post #47
crmd wrote: post #36

Earlier quoted context omitted.

Reminds me of when I started working on storage systems as a young man and once suggested pre-computing every 4KB block once and just using pointers to the correct block as data is written, until someone pointed out that the number of unique 4KB blocks (2^32768) far exceeds the number of atoms in the universe.

Reminds me of when I imagined brute-forcing every possible small picture as simply 256 shades of gray for each pixel x (640 x 480 = 307200 pixels) = 78 million possible pictures. Actually I don't have any intuition for why that's wrong, except that if we catenate the rows into one long row then the picture can be considered as a number 307200 digits long in base 256, and then I see that it could represent 256^307200…

I had friend who had the same idea to do it for pixel fonts with only two colors and 16x16 canvas. It was still 2^256. Watching that thing run and trying to estimate when it would finish made me understand encryption.

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

#79

Post by danwills »

jodrellblank wrote: post #47
crmd wrote: post #36

Earlier quoted context omitted.

Reminds me of when I started working on storage systems as a young man and once suggested pre-computing every 4KB block once and just using pointers to the correct block as data is written, until someone pointed out that the number of unique 4KB blocks (2^32768) far exceeds the number of atoms in the universe.

Reminds me of when I imagined brute-forcing every possible small picture as simply 256 shades of gray for each pixel x (640 x 480 = 307200 pixels) = 78 million possible pictures. Actually I don't have any intuition for why that's wrong, except that if we catenate the rows into one long row then the picture can be considered as a number 307200 digits long in base 256, and then I see that it could represent 256^307200…

Yeah I had a similar thought back in the 90s and made a program to iterate through all possible images at a fairly low res, I left it running while I was at school and got home after many hours to find it had hardly got past the first row of pixels! This was a huge eye-opener about how big a possibility-space digital images really exist in!
Post reply on HN