The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time.Does it hold in some way if the space is limited asymptotically?How does $\textrm{DTISP}(g(n), O(s(n)))$ relate to $\textrm{DTISP}(f(n), O(s(n)))$ if $\frac{f}{g}$ grows fast enough?I am especially interested in the case that $s(n) = n$, $g(n) = n^3$ and $f(n) = 2^n$.In particular, I considered the following language:$ L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w)  \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps}, $ $ k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \} $However, $L_k$ could be decided in $n^3$ steps by using $(k+1)n \in O(n)$ space.Without limiting $M$ to four tape symbols and thus allowing to compress $O(n)$ cells into $n$ cells, we get space issues when simulating an $M$ with too many tape symbols. In this case, the language is not in $\text{DSPACE}(O(n))$ anymore. The same happens when setting $k = h(|w|)$ for some $h$ that can be computed fast enough.This question is basically a rephrase of my question here.Edit Summary:Changed $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ to $\textrm{DTISP}(f(n), s(n))$, however, I think the intersection is also worth to think about.
Time Hierarchies in DSPACE(O(s(n)))
cc.complexity theory;complexity classes;turing machines;space bounded;time hierarchy