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

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

<p>Now, consider a Turing machine $M$ deciding the language.</p>

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

<p>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.)</p>

CC BY-SA 3.0
2017-09-17T07:34:59.873Z
I don't understand the last sentence. Where do we get lower bounds on the running time of $M$?
Emil Jeřábek
CC BY-SA 3.0
2017-09-17T08:16:30.617Z
@EmilJeřábek I clarified the answer.  Let me know if it can be improved further.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-17T09:42:48.747Z
Pethaps I don't understand what "but we can still halt in..." means. What, exactly, does M' do?
Emil Jeřábek
CC BY-SA 3.0
2017-09-17T10:49:30.233Z
@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.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-17T05:52:45.217Z
2017-09-17T08:10:34.763Z
2017-09-17T08:10:34.763Z
Dmytro Taranovsky
<p>I expect the answer is no, but I could not actually construct a counterexample.  The difference is that in $∩_{ε&gt;0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ algorithm uniformly in $ε$.</p>

<p>By a dovetailing argument (for example, see this <a href="https://cstheory.stackexchange.com/questions/14030/under-what-circumstances-do-ona-epsilon-algorithms-imply-onao1">question</a>), if there is a c.e. set of Turing machines $M_i$ deciding a language $L$ such that $∀ε&gt;0 ∃M_i ∈ O(n^{2+ε})$, then $L$ is in $\mathrm{DTIME}(n^{2+o(1)})$.</p>

<p>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 $∩_{ε&gt;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.</p>

<p>The problem would also be solved if we find a sequence of languages $L_i$ such that<br/>
* $L_i$ has a natural $O(n^{2+1/i})$ decision algorithm (uniformly in $i$).<br/>
* Each $L_i$ is finite.<br/>
* 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).</p>

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

CC BY-SA 3.0
2017-09-17T06:46:23.023Z
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?
Michael Wehar
CC BY-SA 3.0
2017-09-17T08:26:50.850Z
@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.
Dmytro Taranovsky
<cc.complexity-theory><time-complexity>
Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
Dmytro Taranovsky
# Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?

(Asked by: username_0 on 2017-09-15)

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](https://cstheory.stackexchange.com/questions/14030/under-what-circumstances-do-ona-epsilon-algorithms-imply-onao1)), 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).

**Tags:** cc.complexity-theory, time-complexity
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_0 on 2017-09-17. Score: 10 | Accepted answer

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 $
     halt iff $M$ says that we do not halt but we can still halt in $

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

> **Comments:**
> **username_2**: I don't understand the last sentence. Where do we get lower bounds on the running time of $M$?  
> **username_0**: @EmilJeřábek I clarified the answer.  Let me know if it can be improved further.  
> **username_2**: Pethaps I don't understand what "but we can still halt in..." means. What, exactly, does M' do?  
> **username_0**: @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.  

---

