zlacker

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.

>>LPisGo+(OP)
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.

>>LPisGo+(OP)
But you also spend time on updating cells, so it is not that intuitive.

>>thatgu+r1
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....

>>qbane+32
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.

>>dragon+52
This article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.

>>thatgu+r1
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.

>>LPisGo+C2
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).

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

>>LPisGo+(OP)
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.

>>hn_acc+H7
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

>>thatgu+r1
There's not even a proof that P != EXPTIME haha

EDIT: I am a dumbass and misremembered.

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

>>delusi+x6
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.

>>LPisGo+(OP)
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.

>>frollo+ag
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.)

>>porphy+Ga
I thought there was some simple proof of this, but all I can think of is time hierarchy theorem.

>>frollo+ag
On the other hand, actual computers can work in parallel when you scale the hardware, something that the TM formulation doesn't cover. It can be interesting which algorithms work well with lots of computing power subject to data locality. (Brains being the classic example of this.)

>>cperci+5j
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.

>>Legion+Cj
Multitape TMs are pretty well studied

>>frollo+om
Spatial position has nothing (ok only a little) to do with topology of connections.

>>cperci+5j
More fundamentally O(n^(1/2)) due to the holographic principle which states that the maximal amount of information encodable in a given region of space scales wrt its surface area, rather than its volume.

(Even more aside to your practical heat dissipation constraint)

>>frollo+om
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)

>>LPisGo+(OP)
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.

>>manwe1+6A
You can add floors though. Some datacenters are 8 stories with cross-floor network fabrics.

>>mpotea+Hp
Hmm, I'll go with that

>>LPisGo+(OP)
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.

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

>>frollo+EH
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.

>>Almond+C5
In other words M <= T.

>>Almond+C5
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.

>>hn_acc+H7
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.

>>hn_acc+H7
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.

>>immibi+481
Oh right, so the height is practically a constant. Square root for sure then.

>>mpotea+Hp
Just need to make sure all your computation is done in a volume with infinite surface area and zero volume. Encoding problem solved. Now then, how hyperbolic can we make the geometry of spacetime before things get too weird?

>>frollo+ZR1
All algorithms are O(1) in this case

>>LPisGo+nL2
You pick what things are constant and what's variable. If you're scaling a supercomputer to fit a problem, the height is going to max out quickly and can be treated as constant, while the other dimensions are variable.

>>within+rD1
>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.

>>Almond+3K3
> Also, "clearly" is not an argument.

As in your assertion is literally self-evidently false. It is on you to provide a burden of proof here; especially since there are instructions that can load more than a single bit of memory.

> How can you access a piece of memory without issuing an instruction to the CPU?

Let me rather ask you this: where do the instructions exist that are running? That is right: in memory. However, just because instructions exist in memory doesn’t mean they’re accessed. There is not a relationship between the number of instructions and the amount of memory accessed/used.

>>within+kS4
This is about time and memory complexity, which is a formal field of computer science. Your replies are about your own vague understanding of computing, which is not the topic here.

>>Almond+hc5
Yes, but you are asserting the relationship is directly connected -- which is clearly not true. You said that it is O(n) memory and O(n) time, both using n. That means a program containing x bytes can only run for x seconds. This is clearly not true.

>>within+KV7
>That means a program containing x bytes can only run for x seconds.

That is not what it means. Again, if you are not familiar with the notation then all you are doing is slapping your personal ideas about computing to some symbols

>>Almond+DT8
Hmm. Telling me I'm 'stupid' doesn't make you right.