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

Improve this question
$\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$
    – Suresh Venkat
    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$
    – Artem Kaznatcheev ♦
    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$
    – Derrick Stolee
    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$
    – Suresh Venkat
    Jan 26, 2011 at 21:55
  • 2
    $\begingroup$ Related? Space-time tradeoff lower bounds $\endgroup$
    – Tsuyoshi Ito
    Jan 27, 2011 at 10:12

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Artem Kaznatcheev ♦
    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))$

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I don't see how this applies to time-space trade-offs... $\endgroup$
    – Artem Kaznatcheev ♦
    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
    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$
    – Artem Kaznatcheev ♦
    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
    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
    Jan 13, 2012 at 17:36

Your Answer

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

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