0
$\begingroup$

Is there a uniform notation, dependent on the fixed function $f$, for the space $\operatorname{DTIME}(f(n))\cap \operatorname{DSPACE}(f(n))$ (for example, when $f(n)=n$ or $f(n)=n^2$ or $f(n)=e^n$, etc.) That is, is there a notation which relates time complexity with space complexity, for a fixed function?

By $\operatorname{DTIME}$ I mean the class of algorithms that take $K$-time to run on a deterministic Turing machine, and by $\operatorname{DSPACE}$ I mean the class of algorithms that take $K$ amount of memory to run on a deterministic Turing machine.

For example, are there names for the following spaces:

  • $\operatorname{DTIME}(n)\cap \operatorname{DSPACE}(n)$
  • $\operatorname{DTIME}(n^2)\cap \operatorname{DSPACE}(n^2)$
  • $\operatorname{P}\cap \operatorname{PSPACE}$
$\endgroup$
1
  • $\begingroup$ Just in case noone answers: maybe "Theoretical Computer Science StackExchange" is a better place to ask. $\endgroup$
    – M. Winter
    Commented Oct 17, 2017 at 12:02

1 Answer 1

1
$\begingroup$

Clearly, everything that can be accomplished in $DTIME(f(x))$ can be accomplished in $DSPACE(f(x))$ since the worst case is to write in memory at each step, and if we assume that the procedure needs $O(f(x))$ time, then it cannot write more that $O(f(x))$ symbols. Hence $$DTIME(f(x)) \cap DSPACE(f(x)) = DTIME(f(x))$$


Note that in general we have $$DTIME(f(x)) \subseteq DSPACE(f(x)) \subseteq DTIME(2^{f(x)})$$ assuming the TM halts. Otherwise it will cycle through the combinations of all of its states and run indefinitely. (My argument is clearly hand-wavy here, but this is not the heart of the question of the OP !)

$\endgroup$
1
  • $\begingroup$ This makes perfect sense, thanks. $\endgroup$
    – user1729
    Commented Oct 17, 2017 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .