14

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
  • Are you asking about an arbitrary L, or are you interested in results of this nature that might exist for specific problems ? – Suresh Venkat Jan 26 '11 at 00: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. – Artem Kaznatcheev Jan 26 '11 at 01:21
  • 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?) – Derrick Stolee 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 – Suresh Venkat Jan 26 '11 at 21:55
  • @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 Jan 27 '11 at 03:01
  • @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 Jan 27 '11 at 03:06
  • 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 Jan 27 '11 at 03:20
  • @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 Jan 27 '11 at 05:12
  • 2
    Related? Space-time tradeoff lower bounds – Tsuyoshi Ito Jan 27 '11 at 10:12
  • Do I miss something or is your restriction analoguous to $L \in DTIME(\Theta(f(n))) \cap DSPACE(\Theta(g(n)))$? – Raphael Jan 27 '11 at 14:43

2 Answers2

14

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.

Noam
  • 9,369
  • 47
  • 58
  • 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 Aug 14 '11 at 20:50
-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))$

Community
  • 1
vzn
  • 11,014
  • 2
  • 31
  • 64
  • 1
    I don't see how this applies to time-space trade-offs... – Artem Kaznatcheev Jan 09 '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
  • 1
    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 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
  • 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 Jan 13 '12 at 18:43
  • 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 (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 Jan 14 '12 at 17:16