I expect the answer is no, but I could not actually construct a counterexample. The difference is that in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ algorithm uniformly in $ε$.

By a dovetailing argument (for example, see this question), if there is a c.e. set of Turing machines $M_i$ deciding a language $L$ such that $∀ε>0 ∃M_i ∈ O(n^{2+ε})$, then $L$ is in $\mathrm{DTIME}(n^{2+o(1)})$.

Given a Turing machine, whether the machine runs in time $n^{2+o(1)}$ is $Π^0_3$-complete. Whether a language (given a code for a machine recognizing it) is in $\mathrm{DTIME}(n^{2+o(1)})$ is $Σ^0_4$ (and $Π^0_3$-hard); whether a language is in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$ is $Π^0_3$-complete. If we can prove $Σ^0_4$ completeness (or just $Σ^0_3$-hardness) of $\mathrm{DTIME}(n^{2+o(1)})$, that would solve the problem, but I am not sure how to do that.

The problem would also be solved if we find a sequence of languages $L_i$ such that
* $L_i$ has a natural $O(n^{2+1/i})$ decision algorithm (uniformly in $i$).
* Each $L_i$ is finite.
* Not only is the size of $L_i$ undecidable, but an algorithm cannot rule out $w∈L_i$ much faster than $O(n^{2+1/i})$ (for worst case $w$), except for finitely many $i$ (dependent on the algorithm).

I am also curious whether there any notable/interesting examples (for $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) \setminus \mathrm{DTIME}(n^{2+o(1)})$ or an analogous relation).

  • $\begingroup$ I've never thought about decidability questions such as given a Turing machine, does it recognize a language in $DTIME(n^{2+o(1)})$. Very neat! Was there a particular reason why you chose 2 in the exponent? I'm guessing this would be roughly the same if you considered some other number in the exponent that was greater than 2? $\endgroup$ Commented Sep 17, 2017 at 6:46
  • 1
    $\begingroup$ @MichaelWehar I just wanted a concrete example, and '1' is sometimes special, so I chose '2'. The completeness properties above and the answer below are quite general. $\endgroup$ Commented Sep 17, 2017 at 8:26

1 Answer 1


Here is a counterexample, i.e. a language with an $O(n^{2+ε})$ algorithm (using multitape Turing machines) for every $ε>0$, but not uniformly in $ε$:
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $m^{2+1/k}$ steps on the empty input. Other strings are rejected.

For every $ε$, we get an $O(n^{2+ε})$ algorithm by hardcoding all sufficiently small nonhalting machines, and simulating the rest.

Now, consider a Turing machine $M$ deciding the language.

Let $M'$ (on the empty input) be an efficient implementation of the following:
for $n$ in 1,2,4,8,...:
     use $M$ to decide whether $M'$ halts in $<n^{2+1/M'}$ steps.
     halt iff $M$ says that we do not halt but we can still halt in $<n^{2+1/M'}$ steps.

By correctness of $M$, $M'$ does not halt, but $M$ takes $Ω(n^{2+1/M'})$-steps on input $0^{M'} 1^{n-M'}$ for infinitely many $n$. (If $M$ is too fast, then $M'$ would contradict $M$. The $Ω(n^{2+1/M'})$ bound depends on $M'$ simulating $M$ in linear time and otherwise being efficient.)

  • $\begingroup$ I don't understand the last sentence. Where do we get lower bounds on the running time of $M$? $\endgroup$ Commented Sep 17, 2017 at 7:34
  • $\begingroup$ @EmilJeřábek I clarified the answer. Let me know if it can be improved further. $\endgroup$ Commented Sep 17, 2017 at 8:16
  • 1
    $\begingroup$ Pethaps I don't understand what "but we can still halt in..." means. What, exactly, does M' do? $\endgroup$ Commented Sep 17, 2017 at 9:42
  • $\begingroup$ @EmilJeřábek M' uses no input and repeatedly calls M to decide bounded halting problem for M'. If, for example, after running for 900 steps, M' discovers that (according to M) M' does not halt in the first 1000 steps, then M' halts. If not, then M' keeps running and calls M to decide whether M' halts in the first 4000 steps or so. $\endgroup$ Commented Sep 17, 2017 at 10:49

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.