Space-time tradeoff and the best algorithm

Consider some language $L$ such that:

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

and so that

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

In other words, the fastest machine $M$ computes $L$ in time $O(f(n))$ and the most space efficient machine $M'$ computes $L$ while using space $O(g(n))$.

What can be said about the space efficiency of M or the time efficiency of M'? Or more precisely, if $\mathbb{M}_T$ is the set of all machines that compute $L$ in $O(f(n))$ then what can we say about the most space efficient machine in $\mathbb{M}_T$? What about the same thing for the obvious space version: $\mathbb{M}_S$.

Alternatively, can $f(n)$ and $g(n)$ be used to define some good space-time tradeoffs? Under what conditions is $TS \in o(f(n)g(n))$ or more generally for some space-time tradeoff $h(T,S)$ under what conditions is $h(T,S) \in h(o(f(n)),o(g(n)))$.

• Are you asking about an arbitrary L, or are you interested in results of this nature that might exist for specific problems ? Jan 26 '11 at 0:38
• I am interested in both, really. My original motivation was mostly from reachability problems (directed and undirected st-connectivity). However, it would be interesting to know if there are any general bounds or techniques available. Jan 26 '11 at 1:21
• So, take any decidable language $L$. This language gives functions $f_L, g_L$ so that $L \in \text{TIME}[f_L(n)] \cap \text{SPACE}[g_L(n)]$ and $L \not\in \text{TIME}[o(f_L(n))] \cup \text{SPACE}[o(g_L(n))]$. (Is this true, or are there "speedup" languages that violate it?) Jan 26 '11 at 15:30
• Specifically, there are examples in range searching of problems that admit (Query, Space) of the form (log n, poly(n)), or (sublinear, linear), or any interpolation thereof Jan 26 '11 at 21:55
• Related? Space-time tradeoff lower bounds Jan 27 '11 at 10:12

The prototypical f and g here would probably be poly-time and polylog space. The interesting problem here is connectivity (in directed graphs) which can be solved in polynomial time (using linear space) or in polylog space (using super-polynomial time). It is a famous open problem whether it can be solved in TIME-SPACE(poly,polylog), a class known as SC.

I.e. your question is a well-known open problem. I don't think that anything non-trivial is known here.

• thanks for the answer. I was suspecting it would be an open problem, but hoping that some specific results would be know already. Unfortunate :(. Aug 14 '11 at 20:50

this question turned up on "similar questions" when I just posted this other question https://cstheory.stackexchange.com/questions/9677/deterministic-time-space-separation-via-space-compression.

there I cite hopcroft,paul,valiants 1977 result (apparently best known acc. to rj lipton in his blog) that seems to apply to your question ie $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

• I don't see how this applies to time-space trade-offs... Jan 9 '12 at 20:56
• the concept of "time space tradeoff" seems not to be exactly defined. my answer can be understood as follows: a program that is in DTIME(t(n)) is "naturally" in DSPACE(t(n)). the HPV1977 results then allow one to construct a TM, at the expense of some increase in states (and tapes maybe?) such that it takes DSPACE(t(n)/log(n)) space instead. therefore a "tradeoff"
– vzn
Jan 13 '12 at 16:17
• There is a standard understanding of trade-offs in CS which is not at all what you describe (what you describe is not a trade-off at all, but just a standard relationship between DTIME and DSPACE). Further, I explicitly explain what I want in time-space trade-off in my question, please read questions carefully before trying to answer them. Jan 13 '12 at 16:56
• if your definition of time-space tradeoffs above in your question is standard as you say, is it defined in any literature?
– vzn
Jan 13 '12 at 17:08
• looking over your definition it looks intuitively plausible that such f(n),g(n) exist for all decidable languages but wouldnt one run into problems even proving such f(n),g(n) necessarily exist due to the blum speedup theorem....?
– vzn
Jan 13 '12 at 17:36