34 ms·

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 con

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.

thatguysaguy 1y ago
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
- dragontamer 1y ago
  The article is about a new proof wherein P == PSPACE. Something we all intuitively expected but someone finally figured out an obscure way to prove it. -------- This is a really roundabout article that takes a meandering path to a total bombshell in the field of complexity theory. Sorry for spoiling but uhhh, you'd expect an article about P == PSPACE would get to the point faster....
  - LPisGood 1y ago
    This article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.
- LPisGood 1y ago
  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.
- porphyra 1y ago
  There's not even a proof that P != EXPTIME haha EDIT: I am a dumbass and misremembered.
  - doc_manhat 1y ago
    I think there is right? It's been a long time but I seem to remember it following from the time hierarchy theorem
  - LPisGood 1y ago
    I thought there was some simple proof of this, but all I can think of is time hierarchy theorem.
deleted 1y ago
[deleted]
qbane 1y ago
But you also spend time on updating cells, so it is not that intuitive.
- LPisGood 1y ago
  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.
  - Almondsetat 1y ago
    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 1y ago
      [deleted]
    - bmacho 1y ago
      In other words M <= T.
    - withinboredom 1y ago
      This is pretty easy to refute: > If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.[sic] This is clearly refuted by all software running today. Programs (especially games) clearly use more memory than there are instructions in the program. > If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time). Memory bombs use an incredible amount of memory and do it incredibly quickly.
      - Almondsetat 1y ago
        >Programs (especially games) clearly use more memory than there are instructions in the program. How can you access a piece of memory without issuing an instruction to the CPU? Also, "clearly" is not an argument. >Memory bombs use an incredible amount of memory and do it incredibly quickly. How can you access a piece of memory without issuing an instruction to the CPU? Also "incredibly quickly" is not an argument. Also also, O(n) is incredibly quick.
hn_acc1 1y ago
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.
- slt2021 1y ago
  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
- benchloftbrunch 1y ago
  As I understand it, this is the essential insight behind dynamic programming algorithms; the whole idea is to exploit the redundancies in a recursive task by memoizing the partial results of lower order stages.
- RetroTechie 1y ago
  There's many algorithms with a space vs time tradeoff. But what works best, depends a lot on the time/energy cost of re-computing something, vs the storage/bandwidth cost of caching results. Expensive calculation, cheap storage → caching results helps. Limited bandwidth / 'expensive' storage, simple calculation (see: today's hyper-fast CPU+L1 cache combo's) → better to re-compute some things on the fly as needed. I suspect there's a lot of existing software (components) out there designed along the "save CPU cycles, burn storage" path, where in modern reality a "save storage, CPU cycles are cheap" would be more effective. CPU speeds have grown way way faster than main memory bandwidth (or even size?) over the last decades. For a datacenter, supercomputer, embedded system, PC or some end-user's phone, the metrics will be different. But same principle applies.
frollogaston 1y ago
Also, the O(1) random memory access assumption makes it easy to take memory for granted. Really it's something like O(n^(1/3)) when you're scaling the computer to the size of the problem, and you can see this in practice in datacenters. I forget the name of the O(1) access model. Not UMA, something else.
- cperciva 1y ago
  O(n^(1/2)) really, since data centers are 2 dimensional, not 3 dimensional. (Quite aside from the practical "we build on the surface of the earth" consideration, heat dissipation considerations limit you to a 2 dimensional circuit in 3-space.)
  - frollogaston 1y ago
    If you have rows of racks of machines, isn't that 3 dimensions? A machine can be on top of, behind, or next to another that it's directly connected to. And the components inside have their own non-uniform memory access. Or if you're saying heat dissipation scales with surface area and is 2D, I don't know. Would think that water cooling makes it more about volume, but I'm not an expert on that.
    - jvanderbot 1y ago
      Spatial position has nothing (ok only a little) to do with topology of connections.
    - manwe150 1y ago
      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)
      - frollogaston 1y ago
        You can add floors though. Some datacenters are 8 stories with cross-floor network fabrics.
undefuser 1y ago
I think it really depends on the task at hand, and not that intuitive. At some point accessing the memory might be slower than repeating the computation, especially when the storage is slow.
IsTom 1y ago
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.

thatguysaguy 1y ago

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

dragontamer 1y ago
The article is about a new proof wherein P == PSPACE. Something we all intuitively expected but someone finally figured out an obscure way to prove it. -------- This is a really roundabout article that takes a meandering path to a total bombshell in the field of complexity theory. Sorry for spoiling but uhhh, you'd expect an article about P == PSPACE would get to the point faster....
- LPisGood 1y ago
  This article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.
LPisGood 1y ago
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.
porphyra 1y ago
There's not even a proof that P != EXPTIME haha EDIT: I am a dumbass and misremembered.
- doc_manhat 1y ago
  I think there is right? It's been a long time but I seem to remember it following from the time hierarchy theorem
- LPisGood 1y ago
  I thought there was some simple proof of this, but all I can think of is time hierarchy theorem.

deleted 1y ago

[deleted]

qbane 1y ago

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

LPisGood 1y ago
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.
- Almondsetat 1y ago
  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 1y ago
    [deleted]
  - bmacho 1y ago
    In other words M <= T.
  - withinboredom 1y ago
    This is pretty easy to refute: > If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.[sic] This is clearly refuted by all software running today. Programs (especially games) clearly use more memory than there are instructions in the program. > If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time). Memory bombs use an incredible amount of memory and do it incredibly quickly.
    - Almondsetat 1y ago
      >Programs (especially games) clearly use more memory than there are instructions in the program. How can you access a piece of memory without issuing an instruction to the CPU? Also, "clearly" is not an argument. >Memory bombs use an incredible amount of memory and do it incredibly quickly. How can you access a piece of memory without issuing an instruction to the CPU? Also "incredibly quickly" is not an argument. Also also, O(n) is incredibly quick.

hn_acc1 1y ago

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.

slt2021 1y ago
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
benchloftbrunch 1y ago
As I understand it, this is the essential insight behind dynamic programming algorithms; the whole idea is to exploit the redundancies in a recursive task by memoizing the partial results of lower order stages.
RetroTechie 1y ago
There's many algorithms with a space vs time tradeoff. But what works best, depends a lot on the time/energy cost of re-computing something, vs the storage/bandwidth cost of caching results. Expensive calculation, cheap storage → caching results helps. Limited bandwidth / 'expensive' storage, simple calculation (see: today's hyper-fast CPU+L1 cache combo's) → better to re-compute some things on the fly as needed. I suspect there's a lot of existing software (components) out there designed along the "save CPU cycles, burn storage" path, where in modern reality a "save storage, CPU cycles are cheap" would be more effective. CPU speeds have grown way way faster than main memory bandwidth (or even size?) over the last decades. For a datacenter, supercomputer, embedded system, PC or some end-user's phone, the metrics will be different. But same principle applies.

frollogaston 1y ago

Also, the O(1) random memory access assumption makes it easy to take memory for granted. Really it's something like O(n^(1/3)) when you're scaling the computer to the size of the problem, and you can see this in practice in datacenters. I forget the name of the O(1) access model. Not UMA, something else.

cperciva 1y ago
O(n^(1/2)) really, since data centers are 2 dimensional, not 3 dimensional. (Quite aside from the practical "we build on the surface of the earth" consideration, heat dissipation considerations limit you to a 2 dimensional circuit in 3-space.)
- frollogaston 1y ago
  If you have rows of racks of machines, isn't that 3 dimensions? A machine can be on top of, behind, or next to another that it's directly connected to. And the components inside have their own non-uniform memory access. Or if you're saying heat dissipation scales with surface area and is 2D, I don't know. Would think that water cooling makes it more about volume, but I'm not an expert on that.
  - jvanderbot 1y ago
    Spatial position has nothing (ok only a little) to do with topology of connections.
  - manwe150 1y ago
    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)
    - frollogaston 1y ago
      You can add floors though. Some datacenters are 8 stories with cross-floor network fabrics.

undefuser 1y ago

I think it really depends on the task at hand, and not that intuitive. At some point accessing the memory might be slower than repeating the computation, especially when the storage is slow.

IsTom 1y ago

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.