6
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ Hmmm, $f(n) = O(1)$ :). $\endgroup$
    – R B
    Commented Jan 15, 2014 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$ Commented Jan 15, 2014 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
    Commented Jan 16, 2014 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
    Commented Jan 16, 2014 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$ Commented Jan 17, 2014 at 21:19

1 Answer 1

10
$\begingroup$

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

$\endgroup$
0

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.