14
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Are you asking about an arbitrary L, or are you interested in results of this nature that might exist for specific problems ? $\endgroup$ Commented Jan 26, 2011 at 0:38
  • $\begingroup$ 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. $\endgroup$ Commented Jan 26, 2011 at 1:21
  • 2
    $\begingroup$ 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?) $\endgroup$ Commented Jan 26, 2011 at 15:30
  • $\begingroup$ 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 $\endgroup$ Commented Jan 26, 2011 at 21:55
  • 2
    $\begingroup$ Related? Space-time tradeoff lower bounds $\endgroup$ Commented Jan 27, 2011 at 10:12

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks for the answer. I was suspecting it would be an open problem, but hoping that some specific results would be know already. Unfortunate :(. $\endgroup$ Commented Aug 14, 2011 at 20:50
-4
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ I don't see how this applies to time-space trade-offs... $\endgroup$ Commented Jan 9, 2012 at 20:56
  • $\begingroup$ 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" $\endgroup$
    – vzn
    Commented Jan 13, 2012 at 16:17
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 13, 2012 at 16:56
  • $\begingroup$ if your definition of time-space tradeoffs above in your question is standard as you say, is it defined in any literature? $\endgroup$
    – vzn
    Commented Jan 13, 2012 at 17:08
  • $\begingroup$ 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....? $\endgroup$
    – vzn
    Commented Jan 13, 2012 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.