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

  • $\begingroup$ I think it is open question to separate DTime[n] from NTime[n], isn't it? $\endgroup$
    – Kaveh
    Oct 23 '16 at 15:50
  • 3
    $\begingroup$ @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. $\endgroup$
    – Parachutes
    Oct 24 '16 at 16:05
  • $\begingroup$ @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]? $\endgroup$
    – Parachutes
    Oct 24 '16 at 16:09
  • $\begingroup$ 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). $\endgroup$
    – Thomas S
    Oct 25 '16 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.