<p>If $\mathsf{L} = \mathsf{P}$ then $\mathsf{DSPACE}(O(f(n))) = \mathsf{DTIME}(2^{O(f(n)})$ for all time-constructible functions $f(n) \geq \log n$ using standard padding arguments. I am not sure what happens if $f(n)$ is not time-constructible.</p>

<p>If $\mathsf{L} \neq \mathsf{P}$ then $f(n) = \log n$ will be an example. Therefore there is a time-constructable function $f(n)$ where the containment is proper iff the containment is proper for $f(n) = \log n$ .</p>

CC BY-SA 3.0
2014-01-18T16:21:02.920Z
2014-01-18T17:05:17.900Z
2014-01-18T17:05:17.900Z
Lance Fortnow
<p>For $f(n)\ge n$, </p>

<p>$$\mathsf{DSPACE}(f(n)) \subseteq \mathsf{DTIME}(2^{O(f(n))}).$$ </p>

<p>Is there any function $f$ for which this containment is known to be proper?</p>

CC BY-SA 3.0
2014-01-15T07:29:54.440Z
Hmmm, $f(n) = O(1)$ :).
R B
CC BY-SA 3.0
2014-01-15T09:45:27.983Z
@RB The containment is not proper for $f(n)=O(1)$.  In fact, there isn't containment at all: constant space includes all regular languages; constant time includes only those languages decidable by looking at a constant prefix of the string.
David Richerby
CC BY-SA 3.0
2014-01-16T05:39:15.613Z
Yes, you're absolutely right, the containment is only valid for $f(n)\ge n$. I have corrected the question. Thanks!
Siddharth
CC BY-SA 3.0
2014-01-17T21:19:37.447Z
What precisely do you mean with $DTIME(2^{O(f(n))})$?  Do you mean that for every $f$ there is some constant $C_f$ such that $DSPACE(f(n)) \subseteq DTIME(2^{C_f f(n)})$?
András Salamon
CC BY-SA 3.0
2014-01-17T21:30:45.130Z
Yes, that is what I mean.
Siddharth
CC BY-SA 3.0
2014-01-18T10:39:30.287Z
$DTIME(2^{O(f(n))})$ is too imprecise: this is convenient shorthand, but here it matters what it stands for.  A possible phrasing: "For any function $f(n)\ge n$, there exist constants $C$ such that $DSPACE(f(n)) \subseteq DTIME(2^{Cf(n)})$.  Let $c_f$ be the infimum of all such $C$.  Is there a function $f(n) \ge n$ such that $DSPACE(f(n)) \ne DTIME(2^{c_f f(n)})$ is known to hold?"  Note also that by the time hierarchy theorem, $DTIME(2^{cn}) \subsetneq DTIME(2^{(c+\epsilon)n})$ for any $\epsilon > 0$: even if equality holds for some constant, it will not hold for any others.
András Salamon
CC BY-SA 3.0
2014-01-18T19:04:34.593Z
Good point. I disagree with what I said earlier; let me revise what I mean by $DTIME(2^{O(f(n))})$. I mean the union over all $C>0$ of $DTIME(2^{Cf(n)})$.

So what I'm really asking is whether there is some $f$, some $C$, and some language $L \in DTIME(2^{Cf(n)})$ such that $L \notin DSPACE(f(n))$
Siddharth
<cc.complexity-theory><complexity-classes>
Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$?
Siddharth
# Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$?

(Asked by: username_0 on 2014-01-15)

For $f(n)\ge n$,

$$\mathsf{DSPACE}(f(n)) \subseteq \mathsf{DTIME}(2^{O(f(n))}).$$

Is there any function $f$ for which this containment is known to be proper?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Hmmm, $f(n) = O(1)$ :).  
> **username_2**: @RB The containment is not proper for $f(n)=O(1)$.  In fact, there isn't containment at all: constant space includes all regular languages; constant time includes only those languages decidable by looking at a constant prefix of the string.  
> **username_0**: Yes, you're absolutely right, the containment is only valid for $f(n)\ge n$. I have corrected the question. Thanks!  
> **username_3**: What precisely do you mean with $DTIME(2^{O(f(n))})$?  Do you mean that for every $f$ there is some constant $C_f$ such that $DSPACE(f(n)) \subseteq DTIME(2^{C_f f(n)})$?  
> **username_0**: Yes, that is what I mean.  
> **username_3**: $DTIME(2^{O(f(n))})$ is too imprecise: this is convenient shorthand, but here it matters what it stands for.  A possible phrasing: "For any function $f(n)\ge n$, there exist constants $C$ such that $DSPACE(f(n)) \subseteq DTIME(2^{Cf(n)})$.  Let $c_f$ be the infimum of all such $C$.  Is there a function $f(n) \ge n$ such that $DSPACE(f(n)) \ne DTIME(2^{c_f f(n)})$ is known to hold?"  Note also that by the time hierarchy theorem, $DTIME(2^{cn}) \subsetneq DTIME(2^{(c+\epsilon)n})$ for any $\epsilon > 0$: even if equality holds for some constant, it will not hold for any others.  
> **username_0**: Good point. I disagree with what I said earlier; let me revise what I mean by $DTIME(2^{O(f(n))})$. I mean the union over all $C>0$ of $DTIME(2^{Cf(n)})$.  So what I'm really asking is whether there is some $f$, some $C$, and some language $L \in DTIME(2^{Cf(n)})$ such that $L \notin DSPACE(f(n))$  

---

## 1 answers

### Answer by username_4 on 2014-01-18. Score: 10 | Accepted answer

If $\mathsf{L} = \mathsf{P}$ then $\mathsf{DSPACE}(O(f(n))) = \mathsf{DTIME}(2^{O(f(n)})$ for all time-constructible functions $f(n) \geq \log n$ using standard padding arguments. I am not sure what happens if $f(n)$ is not time-constructible.

If $\mathsf{L} \neq \mathsf{P}$ then $f(n) = \log n$ will be an example. Therefore there is a time-constructable function $f(n)$ where the containment is proper iff the containment is proper for $f(n) = \log n$ .


---

