The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?

  • 1
    $\begingroup$ On a single tape machine, the non-regular language $\{A^nB^n | n \geq 0\}$ is easily decidable in TIME[$O(n \log n)$], but all languages decidable in TIME[$o(n \log n)$] are regular. This same argument does not work for multi-tape machines. $\endgroup$ – Yonatan N Sep 29 '18 at 6:09
  • 1
    $\begingroup$ of course, my model of computation is multi-tape Turing machine. $\endgroup$ – YuiTo Cheng Sep 29 '18 at 6:25

For all $a≥0$ and $ε>0$, $\mathrm{DTIME}(O(n \log^{a} n))$ is strictly contained in $\mathrm{DTIME}(O(n \log^{a+ε} n))$; see my answer here.

To recap, the logarithmic overhead comes from tape reduction (and is not needed if the number of tapes is fixed and is at least two). There is a nonconstructive argument that converts the logarithmic overhead into time hierarchy at $\log^{ε} \mathrm{time}$ multiplicative precision for well-behaved (time-constructible and in a certain sense continuous) time bounds.

A constructive proof of the strict inclusion of $\mathrm{DTIME}(O(n))$ in $\mathrm{DTIME}(O(n \log n))$ remains (to my knowledge) an open problem.

  • $\begingroup$ I've checked out your answer and it's nice. But could you elaborate a little bit more about how to use the padding argument? $\endgroup$ – YuiTo Cheng Sep 29 '18 at 17:22
  • $\begingroup$ Also, where does the proof require that f is well-behaved in your sense? $\endgroup$ – YuiTo Cheng Sep 29 '18 at 17:29
  • $\begingroup$ For time-constructible $f(n) > n$, if $\mathrm{Time}(O(f(n))) = \mathrm{Time}(O(n))$, then by padding input to length $f(n)$, $\mathrm{Time}(O(f(f(n)))) = \mathrm{Time}(O(f(n)))$ (and similarly with appropriate $g(n)$ in place of $n$). The 'continuity' of a function $g$ is used to get from $g$ to $>g \log g$ using a finite composition of $f$ with $f(g(n)) < g(n) \log^ε g(n)$. $\endgroup$ – Dmytro Taranovsky Sep 29 '18 at 18:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.