<p>It is known that $\mathrm{DTIME}[n]\subseteq \mathrm{DSPACE}[n/\log n]$. Therefore, there are languages in $\mathrm{DSPACE}[n]$ which are not in 
$\mathrm{DTIME}[o(n\log n)]$.</p>

<ol>
<li><p>Are there examples of "natural" problems which are in 
$\mathrm{DSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$? </p></li>
<li><p>Are there examples of "natural" problems that are in $\mathrm{NSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$? </p></li>
</ol>

<p>By "natural" I mean problems which are not specifically designed to meet the specifications of the question. Clearly, using diagonalization arguments one can cook up problems that are in $\mathrm{DSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$. </p>

<p>Note that the classes DTIME, DSPACE and NSPACE above are defined with respect to multitape turing machines. </p>

<p>Obs 1:  I'm mostly interested in lower bounds of the form $\Omega(n\log n)$ or even $\Omega(n\log \log n)$ for Multitape turing machines. But weaker lower bounds would also be welcome. For instance, it has been shown in 
<a href="http://eccc.hpi-web.de/report/2008/076/" rel="nofollow">this paper</a>, that satisfiability of succint QBF-formulas with a constant number of alternations require time $\Omega(n\log^* n)$, where $\log^* n$ is the <a href="https://en.wikipedia.org/wiki/Iterated_logarithm" rel="nofollow">iterated logarithm function</a>. Although $\log^* n$ grows extremely slowly, this lower bound has the advantage that it works not only for multitape TMs but also for more general models, such as $d$-dimensional TM's, random access TM', and alike.</p>

CC BY-SA 3.0
2016-10-23T15:50:51.587Z
I think it is open question to separate DTime[n] from NTime[n], isn't it?
Kaveh
CC BY-SA 3.0
2016-10-24T16:05:20.623Z
@Kaveh For multitape Turing Machines it is known that NTIME[n] is strictly more powerful than DTIME[n]. There is a language that is in NTIME[n], but not in $DTIME[o(n\cdot (\log^* n)^{1/4})]$. This is an old result due to Paul, Pippenger, Szemeredi and Trotter (FOCS 1983). A similar result is not known for more general machines such as turing machines with random access, or multi-dimensional tapes, etc.
Parachutes
CC BY-SA 3.0
2016-10-24T16:09:21.617Z
@Kaveh, but anyways, I'm curious about why you have asked about the relation between DTIME[n] and NTIME[n]. Am I missing some connection between NTIME[n] and NSPACE[n]?
Parachutes
CC BY-SA 3.0
2016-10-25T20:54:56.987Z
There is  a natural problem, RISA, which is in NTIME(n log n), but not in DTIME(n).  

Given $(Q,\Sigma,\delta,s,F)$, where $\delta$ is only *partial* and a number $k$, it asks whether $\delta$ can be extended to a *total* transition function such that the minimal automaton for the resulting automaton has $\le k$ states. 

That it is not in DTIME(n) is shown in: Etienne Grandjean:
First-Order Spectra with One Variable. J. Comput. Syst. Sci. 40(2): 136-153 (1990). A later paper by Grandjean shows it is in NLINEAR (a nondet. linear time class on a RAM model) and also in NTIME(n log n).
Thomas S
<lower-bounds><complexity>
Natural Problems NSPACE[n] but not in DTIME[n]
Parachutes
# Natural Problems NSPACE[n] but not in DTIME[n]

(Asked by: username_0 on 2016-10-21)

It is known that $\mathrm{DTIME}[n]\subseteq \mathrm{DSPACE}[n/\log n]$. Therefore, there are languages in $\mathrm{DSPACE}[n]$ which are not in
$\mathrm{DTIME}[o(n\log n)]$.

1. Are there examples of "natural" problems which are in
   $\mathrm{DSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$?
2. Are there examples of "natural" problems that are in $\mathrm{NSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$?

By "natural" I mean problems which are not specifically designed to meet the specifications of the question. Clearly, using diagonalization arguments one can cook up problems that are in $\mathrm{DSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$.

Note that the classes DTIME, DSPACE and NSPACE above are defined with respect to multitape turing machines.

Obs 1: I'm mostly interested in lower bounds of the form $\Omega(n\log n)$ or even $\Omega(n\log \log n)$ for Multitape turing machines. But weaker lower bounds would also be welcome. For instance, it has been shown in
[this paper](http://eccc.hpi-web.de/report/2008/076/), that satisfiability of succint QBF-formulas with a constant number of alternations require time $\Omega(n\log^\* n)$, where $\log^\* n$ is the [iterated logarithm function](https://en.wikipedia.org/wiki/Iterated_logarithm). Although $\log^\* n$ grows extremely slowly, this lower bound has the advantage that it works not only for multitape TMs but also for more general models, such as $d$-dimensional TM's, random access TM', and alike.

**Tags:** lower-bounds, complexity
> **Comments:**
> **username_1**: I think it is open question to separate DTime[n] from NTime[n], isn't it?  
> **username_0**: @Kaveh For multitape Turing Machines it is known that NTIME[n] is strictly more powerful than DTIME[n]. There is a language that is in NTIME[n], but not in $DTIME[o(n\cdot (\log^* n)^{1/4})]$. This is an old result due to Paul, Pippenger, Szemeredi and Trotter (FOCS 1983). A similar result is not known for more general machines such as turing machines with random access, or multi-dimensional tapes, etc.  
> **username_0**: @Kaveh, but anyways, I'm curious about why you have asked about the relation between DTIME[n] and NTIME[n]. Am I missing some connection between NTIME[n] and NSPACE[n]?  
> **username_2**: There is  a natural problem, RISA, which is in NTIME(n log n), but not in DTIME(n).    Given $(Q,\Sigma,\delta,s,F)$, where $\delta$ is only *partial* and a number $k$, it asks whether $\delta$ can be extended to a *total* transition function such that the minimal automaton for the resulting automaton has $\le k$ states.   That it is not in DTIME(n) is shown in: Etienne Grandjean: First-Order Spectra with One Variable. J. Comput. Syst. Sci. 40(2): 136-153 (1990). A later paper by Grandjean shows it is in NLINEAR (a nondet. linear time class on a RAM model) and also in NTIME(n log n).  

---

## 0 answers

