<p>This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$.</p>

<p>However, under plausible computational complexity conjectures, there is a proper hierarchy.  For example, if for every $ε&gt;0$, CIRCUIT-SAT ∉ i.o.-$O(2^{n-ε})$, then
$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$<br/>
where $f(n)≥n$, $f(n)$ is $2^{o(\min(n,s(n)))}$, and $f$ is time-space constructible.</p>

<p>In particular (under the hypothesis), existence of a satisfying assignment for circuits with $⌊\mathrm{lg}(f^{1+ε/2})⌋$ inputs and size $(\log f)^{O(1)}$ serves as a counterexample to the equality of the classes.</p>

<p><i>Notes:</i></p>

<ul>
<li><p>CIRCUIT-SAT is at least as hard as $k$-SAT (which is used in the strong exponential time hypothesis).</p></li>
<li><p>Per convention, in CIRCUIT-SAT, $n$ is the number of input wires; circuit size is $n^{O(1)}$.</p></li>
<li><p>If the assumption used CIRCUIT-SAT for quasilinear circuit sizes, then the bound on $f(n)$ can be relaxed to $O((2-ε)^{\min(n,s(n))})$.  Also, weaker/stronger assumptions on hardness of CIRCUIT-SAT give weaker/stronger hierarchies (that we can currently prove).</p></li>
<li><p>i.o. means infinitely often, and can be dropped for $f$ that are in a certain sense continuous (including $f(n)=n^a$).</p></li>
<li><p>It appears likely that the DTISP hierarchy is sharp enough to distinguish $O(f)$ from $o(f/\log f)$ (and perhaps $o(f)$) (when $f$ is not too large relative to the permitted space).</p></li>
<li><p>To distinguish $n^a$ from $2^n$, we only need the weaker assumption P≠PSPACE.</p></li>
</ul>

CC BY-SA 3.0
2017-09-22T13:58:02.700Z
2017-09-22T13:58:02.700Z
Dmytro Taranovsky
<p>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?</p>

<p>I am especially interested in the case that $s(n) = n$, $g(n) = n^3$ and $f(n) = 2^n$.</p>

<p>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} \} $</p>

<p>However, $L_k$ could be decided in $n^3$ steps by using $(k+1)n \in O(n)$ space.</p>

<p>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.</p>

<p>This question is basically a rephrase of my question <a href="https://cstheory.stackexchange.com/questions/38592/is-there-a-dcsl-that-cannot-be-recognized-in-on2-steps-by-a-deterministic-lba">here</a>.</p>

<p><em>Edit Summary:</em>
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.</p>

CC BY-SA 3.0
2017-07-21T22:49:19.650Z
Awesome question!!  It's also quite interesting to look at DTISP(g(n), s(n)) vs DTISP(f(n), s(n)) if $\frac{f}{g}$ grows fast enough.  DTISP(g(n), s(n)) represents languages that can be solved by a single algorithm that runs in at most g(n) time using s(n) space while DTIME(g(n)) $\cap$ DSPACE(s(n)) represents languages with two algorithms where one algorithm runs in g(n) time and the other algorithm runs in s(n) space.
Michael Wehar
CC BY-SA 3.0
2017-07-22T00:17:18.557Z
Oops... I actually wrote D-SPACE(O(s(n)))-TIME(g(n)) first, but I didn't like the look of what MathJax made out of it, so I quickly changed it to DSPACE(O(s(n))) ∩ DTIME(g(n)) without thinking much about it.

My initial question is about what I wrote first, but the intersection DSPACE(O(s(n))) ∩ DTIME(g(n)) is also very interesting - I am glad I did this mistake.
Clearly DTISP(g(n), s(n)) ⊆  DTIME(g(n)) ∩ DSPACE(s(n)). Is this a proper inclusion?
According to wikipedia, its properness is unknown for DTISP(P, PolyL) ⊆  DTIME(P) ∩ DSPACE(PolyL): https://www.wikiwand.com/en/SC_(complexity)
Henning
CC BY-SA 3.0
2017-07-22T06:10:09.877Z
Cool!!  Thank you for your clarification.  I'm really interested in these kinds of problems.  :)
Michael Wehar
CC BY-SA 3.0
2017-09-23T19:59:50.233Z
$DTISP(2^n,n)=DSPACE(n)$. So, your second case is trivial.
rus9384
CC BY-SA 3.0
2018-01-02T23:12:51.580Z
It's worth mentioning that a time hierarchy for a fixed amount of space can be obtained for Turing machines with $k$ tapes for fixed $k$ by using arguments similar to Hopcroft-Paul-Valiant and tight time hierarchies for $k$-tape machines. See e.g. W.J. Paul. `On time hierarchies' in STOC’77
Sam McGuire
<cc.complexity-theory><complexity-classes><turing-machines><space-bounded><time-hierarchy>
Time Hierarchies in DSPACE(O(s(n)))
Henning
# Time Hierarchies in DSPACE(O(s(n)))

(Asked by: username_0 on 2017-07-21)

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](https://cstheory.stackexchange.com/questions/38592/is-there-a-dcsl-that-cannot-be-recognized-in-on2-steps-by-a-deterministic-lba).

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

**Tags:** cc.complexity-theory, complexity-classes, turing-machines, space-bounded, time-hierarchy

> **Comments:**
> **username_1**: Awesome question!!  It's also quite interesting to look at DTISP(g(n), s(n)) vs DTISP(f(n), s(n)) if $\frac{f}{g}$ grows fast enough.  DTISP(g(n), s(n)) represents languages that can be solved by a single algorithm that runs in at most g(n) time using s(n) space while DTIME(g(n)) $\cap$ DSPACE(s(n)) represents languages with two algorithms where one algorithm runs in g(n) time and the other algorithm runs in s(n) space.  
> **username_0**: Oops... I actually wrote D-SPACE(O(s(n)))-TIME(g(n)) first, but I didn't like the look of what MathJax made out of it, so I quickly changed it to DSPACE(O(s(n))) ∩ DTIME(g(n)) without thinking much about it.  My initial question is about what I wrote first, but the intersection DSPACE(O(s(n))) ∩ DTIME(g(n)) is also very interesting - I am glad I did this mistake. Clearly DTISP(g(n), s(n)) ⊆  DTIME(g(n)) ∩ DSPACE(s(n)). Is this a proper inclusion? According to wikipedia, its properness is unknown for DTISP(P, PolyL) ⊆  DTIME(P) ∩ DSPACE(PolyL): https://www.wikiwand.com/en/SC_(complexity)  
> **username_1**: Cool!!  Thank you for your clarification.  I'm really interested in these kinds of problems.  :)  
> **username_2**: $DTISP(2^n,n)=DSPACE(n)$. So, your second case is trivial.  
> **username_3**: It's worth mentioning that a time hierarchy for a fixed amount of space can be obtained for Turing machines with $k$ tapes for fixed $k$ by using arguments similar to Hopcroft-Paul-Valiant and tight time hierarchies for $k$-tape machines. See e.g. W.J. Paul. `On time hierarchies' in STOC’77  

---

## 1 answers

### Answer by username_4 on 2017-09-22. Score: 6 | Accepted answer

This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$.

However, under plausible computational complexity conjectures, there is a proper hierarchy. For example, if for every $ε>0$, CIRCUIT-SAT ∉ i.o.-$O(2^{n-ε})$, then
$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$  
where $f(n)≥n$, $f(n)$ is $2^{o(\min(n,s(n)))}$, and $f$ is time-space constructible.

In particular (under the hypothesis), existence of a satisfying assignment for circuits with $⌊\mathrm{lg}(f^{1+ε/2})⌋$ inputs and size $(\log f)^{O(1)}$ serves as a counterexample to the equality of the classes.

*Notes:*

* CIRCUIT-SAT is at least as hard as $k$-SAT (which is used in the strong exponential time hypothesis).
* Per convention, in CIRCUIT-SAT, $n$ is the number of input wires; circuit size is $n^{O(1)}$.
* If the assumption used CIRCUIT-SAT for quasilinear circuit sizes, then the bound on $f(n)$ can be relaxed to $O((2-ε)^{\min(n,s(n))})$. Also, weaker/stronger assumptions on hardness of CIRCUIT-SAT give weaker/stronger hierarchies (that we can currently prove).
* i.o. means infinitely often, and can be dropped for $f$ that are in a certain sense continuous (including $f(n)=n^a$).
* It appears likely that the DTISP hierarchy is sharp enough to distinguish $O(f)$ from $o(f/\log f)$ (and perhaps $o(f)$) (when $f$ is not too large relative to the permitted space).
* To distinguish $n^a$ from $2^n$, we only need the weaker assumption P≠PSPACE.


---

