7
$\begingroup$

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?

$\endgroup$
2
  • 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, 2018 at 6:09
  • 1
    $\begingroup$ of course, my model of computation is multi-tape Turing machine. $\endgroup$ Sep 29, 2018 at 6:25

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Sep 29, 2018 at 17:22
  • $\begingroup$ Also, where does the proof require that f is well-behaved in your sense? $\endgroup$ Sep 29, 2018 at 17:29
  • 1
    $\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$ Sep 29, 2018 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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