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

<p>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))$</p>

CC BY-SA 3.0
2012-01-09T20:56:30.023Z
I don't see how this applies to time-space trade-offs...
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-13T16:17:42.813Z
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
CC BY-SA 3.0
2012-01-13T16:56:24.027Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-13T17:08:57.487Z
if your definition of time-space tradeoffs above in your question is standard as you say, is it defined in any literature?
vzn
CC BY-SA 3.0
2012-01-13T17:36:56.007Z
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
CC BY-SA 3.0
2012-01-13T18:43:45.913Z
actually one statement of the blum speed up thm is that "there exist decidable languages with no fastest machine". therefore I think your functions can be proven not to exist for some decidable languages (re derrick stolee's comment above) – vzn 33 mins ago
vzn
CC BY-SA 3.0
2012-01-14T17:16:53.903Z
the issue of time/space tradeoffs has always been a question for me but wonder if expressing it is actually somewhat "open" and theoretical CS has not well nailed it down yet. fyi I am reading [goldreich's discussion of the hierarchy thms & blums speedup thm](http://www.wisdom.weizmann.ac.il/~oded/cc-drafts.html) (one of the better online referencees) & think you need to add the condition that f,g are time,space constructible respectively to avoid the problem with blums speedup. however, even given that condition its not totally obvious to me that f,g exist & think a proof might not be subtle.
vzn
CC BY-SA 3.0
2012-01-09T19:51:24.890Z
2012-01-09T19:51:24.890Z
2017-04-13T12:32:28.080Z
vzn
<p>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 <a href="http://en.wikipedia.org/wiki/SC_%28complexity%29">SC</a>.</p>

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

CC BY-SA 3.0
2011-08-14T20:50:11.700Z
thanks for the answer. I was suspecting it would be an open problem, but hoping that some specific results would be know already. Unfortunate :(.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-14T20:00:00.573Z
2011-08-14T20:00:00.573Z
Noam
<p>Consider some language $L$ such that:</p>

<p>$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$</p>

<p>and so that</p>

<p>$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$</p>

<p>In other words, the fastest machine $M$ computes $L$ in time $O(f(n))$ and the most space efficient machine $M&#39;$ computes $L$ while using space $O(g(n))$. </p>

<p>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$.</p>

<p>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)))$.</p>

CC BY-SA 2.5
2011-01-26T00:38:29.270Z
Are you asking about an arbitrary L, or are you interested in results of this nature that might exist for specific problems ?
Suresh Venkat
CC BY-SA 2.5
2011-01-26T01:21:29.853Z
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.
Artem Kaznatcheev
CC BY-SA 2.5
2011-01-26T15:30:16.140Z
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?)
Derrick Stolee
CC BY-SA 2.5
2011-01-26T21:55:56.050Z
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
Suresh Venkat
CC BY-SA 2.5
2011-01-27T03:01:21.947Z
@Derrick: I am not exactly sure what you are asking, or if you are restating my question. For a given language $L$ the functions $f_L$ and $g_L$ can (hopefully) be thought of as defined (although obviously finding these functions is way harder than the P vs. NP problem). But I don't think it means that there exists a machine M that solves L that achieves BOTH speed $O(f_L)$ and $O(g_L)$. It just means that there exist machines $M_T$ and $M_S$ for $L$ so that the runtime of $M_T$ is $O(f_L(n))$ and space use of $M_S$ is $O(g_L(N))$. I am not sure what you mean by a "speedup" language.
Artem Kaznatcheev
CC BY-SA 2.5
2011-01-27T03:06:42.037Z
@Suresh: could you elaborate on your comment? Does you mean there are machines M and M' for some range search problem with M having time $O(log n)$ and space $O(poly(n))$ (but not linear) and M' having time $O(f(n))$ for some $f(n) \in o(n) - O(log n)$ and space $O(n)$?
Artem Kaznatcheev
CC BY-SA 2.5
2011-01-27T03:20:58.110Z
I was trying to restate, specifically pointing out that $f$ and $g$ depend on $L$.  I also wanted to ask if EVERY language admits such $f$ and $g$, which may not be true.
Derrick Stolee
CC BY-SA 2.5
2011-01-27T05:12:00.533Z
@Artem, yes, that's correct, and in fact for any tradeoff between these two as well. If that's the kind of thing you're interested in, I can post an answer.
Suresh Venkat
CC BY-SA 2.5
2011-01-27T10:12:08.440Z
Related?  [Space-time tradeoff lower bounds](http://cstheory.stackexchange.com/questions/832/space-time-tradeoff-lower-bounds)
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T14:43:13.827Z
Do I miss something or is your restriction analoguous to $L \in DTIME(\Theta(f(n))) \cap DSPACE(\Theta(g(n)))$?
Raphael
<cc.complexity-theory><ds.algorithms><open-problem><space-time-tradeoff>
Space-time tradeoff and the best algorithm
Artem Kaznatcheev
# Space-time tradeoff and the best algorithm

(Asked by: username_0 on 2011-01-26)

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)))$.

**Tags:** cc.complexity-theory, ds.algorithms, open-problem, space-time-tradeoff

> **Comments:**
> **username_1**: Are you asking about an arbitrary L, or are you interested in results of this nature that might exist for specific problems ?  
> **username_0**: 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.  
> **username_2**: 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?)  
> **username_1**: 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  
> **username_0**: @Derrick: I am not exactly sure what you are asking, or if you are restating my question. For a given language $L$ the functions $f_L$ and $g_L$ can (hopefully) be thought of as defined (although obviously finding these functions is way harder than the P vs. NP problem). But I don't think it means that there exists a machine M that solves L that achieves BOTH speed $O(f_L)$ and $O(g_L)$. It just means that there exist machines $M_T$ and $M_S$ for $L$ so that the runtime of $M_T$ is $O(f_L(n))$ and space use of $M_S$ is $O(g_L(N))$. I am not sure what you mean by a "speedup" language.  
> **username_0**: @Suresh: could you elaborate on your comment? Does you mean there are machines M and M' for some range search problem with M having time $O(log n)$ and space $O(poly(n))$ (but not linear) and M' having time $O(f(n))$ for some $f(n) \in o(n) - O(log n)$ and space $O(n)$?  
> **username_2**: I was trying to restate, specifically pointing out that $f$ and $g$ depend on $L$.  I also wanted to ask if EVERY language admits such $f$ and $g$, which may not be true.  
> **username_1**: @Artem, yes, that's correct, and in fact for any tradeoff between these two as well. If that's the kind of thing you're interested in, I can post an answer.  
> **username_3**: Related?  [Space-time tradeoff lower bounds](http://cstheory.stackexchange.com/questions/832/space-time-tradeoff-lower-bounds)  
> **username_4**: Do I miss something or is your restriction analoguous to $L \in DTIME(\Theta(f(n))) \cap DSPACE(\Theta(g(n)))$?  

---

## 2 answers

### Answer by username_6 on 2011-08-14. Score: 14 | Accepted answer

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](http://en.wikipedia.org/wiki/SC_%28complexity%29).

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

> **Comments:**
> **username_0**: thanks for the answer. I was suspecting it would be an open problem, but hoping that some specific results would be know already. Unfortunate :(.  

---

### Answer by username_5 on 2012-01-09. Score: -4

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))$

> **Comments:**
> **username_0**: I don't see how this applies to time-space trade-offs...  
> **username_5**: 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"  
> **username_0**: 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.  
> **username_5**: if your definition of time-space tradeoffs above in your question is standard as you say, is it defined in any literature?  
> **username_5**: 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....?  
> **username_5**: actually one statement of the blum speed up thm is that "there exist decidable languages with no fastest machine". therefore I think your functions can be proven not to exist for some decidable languages (re derrick stolee's comment above) – username_5 33 mins ago  
> **username_5**: the issue of time/space tradeoffs has always been a question for me but wonder if expressing it is actually somewhat "open" and theoretical CS has not well nailed it down yet. fyi I am reading [goldreich's discussion of the hierarchy thms & blums speedup thm](http://www.wisdom.weizmann.ac.il/~oded/cc-drafts.html) (one of the better online referencees) & think you need to add the condition that f,g are time,space constructible respectively to avoid the problem with blums speedup. however, even given that condition its not totally obvious to me that f,g exist & think a proof might not be subtle.  

---

