This paper people.csail.mit.edu/rrw/time-vs-... (circulated on Mastodon) is pretty incredible. It is obvious that DTIME(f(n)) ⊆ DSPACE(f(n)). The author proves that DTIME(f(n)) ⊆ DSPACE(√(f(n) log(f(n)))) for f(n) ≥ n 😱 I am dumbfounded that this is true and even more that it is both true and new. - ThreadSky

jeanas.bsky.social • 9 days ago

This paper https://people.csail.mit.edu/rrw/time-vs-space.pdf (circulated on Mastodon) is pretty incredible.

It is obvious that DTIME(f(n)) ⊆ DSPACE(f(n)). The author proves that DTIME(f(n)) ⊆ DSPACE(√(f(n) log(f(n)))) for f(n) ≥ n 😱

I am dumbfounded that this is true and even more that it is both true and new.

Comments

shab0y.bsky.social•9 days ago

In crypto there are some problems for which the tradeoff TM = N is provably optimal (in some computational model, in some sense) so a quadratic gap makes sense to me. But that doesn't mean that the existence of a general result does not surprise/amaze me!

jeanas.bsky.social•9 days ago

What do you mean by TM = N ?

shab0y.bsky.social•9 days ago

T = time cost, M (<= T) = memory cost, N = instance size (or any function of it, e.g. a log)
So if you have a continuous tradeoff curve TM = N for a problem, you can choose to solve it memorylessly for a time cost N, or for cost \sqrt{N} if you also store that much in memory

frizlab.me•9 days ago

I have no idea what any of this means.

jeanas.bsky.social•9 days ago

Sorry, I should probably have a bio to warn that I tend to post for a math/CS audience.

It means this: assume you have a computational problem which asks to produce some output given some input. (Cliché example: input is a list of numbers, output should be the same list in sorted order.)

jeanas.bsky.social•9 days ago

Assume that you are able to solve the problem with an algorithm that takes f(n) computation steps (“time”) to compute the output, where n is the size of the input. (Of course f(n) normally increases: larger inputs take more time to process.)

jeanas.bsky.social•9 days ago

Then it is easy to see that you can solve the same problem with an algorithm that consumes at most f(n) cells of memory (“space”): you can simply take the same algorithm, because if it does f(n) computation steps, as a step is needed to consume a memory cell, it won't consume more than f(n) cells.

jeanas.bsky.social•9 days ago

What the theorem says is that you can transform the algorithm to get a new algorithm (quite possibly different than the original) which consumes only sqrt(f(n) log(f(n))) memory cells.

jeanas.bsky.social•9 days ago

This is quite surprising because this amount of memory is much lower than f(n). Also, it breaks assumptions that were not proven but which people have been working under in complexity theory.

Comments

Posting Rules

Reply