# Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$?

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?

• Hmmm, $f(n) = O(1)$ :). – R B Jan 15 '14 at 7:29
• @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 Jan 15 '14 at 9:45
• Yes, you're absolutely right, the containment is only valid for $f(n)\ge n$. I have corrected the question. Thanks! – Siddharth Jan 16 '14 at 5:39
• I'm pretty sure it's valid for $\:\: f(n) \: \geq \: c\hspace{-0.03 in}\cdot \hspace{-0.03 in}\log(n)\;\;$. $\;\;\;\;\;\;$ – user6973 Jan 16 '14 at 7:33
• 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 Jan 17 '14 at 21:19

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