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?

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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