<p>You can use Levin's universal search algorithm. Suppose that you can somehow enumerate a sequence of algorithms $A_k$ deciding $L$, each running in time $C_k n^{a+1/k}$. Levin's algorithm runs in time $T(n) \leq D_k n^{a+1/k}$ for every $k$, where $D_k$ is a constant depending on $C_k$. So for every $k$,
$$ \tau(n) \triangleq \frac{\log T(n)}{\log n} - a \leq \frac{\log D_k + (a+1/k) \log n}{\log n} - a = \frac{\log D_k}{\log n} + \frac{1}{k}. $$
Given $\epsilon&gt;0$, choose $k = \lceil 2/\epsilon \rceil$, and let $N = \lceil D_k^{2/\epsilon} \rceil$. Then for $n \geq N$, $\tau(n) \leq \epsilon$. Therefore $\tau(n) \rightarrow 0$, and we get that Levin's algorithm runs in time $n^{a+\tau(n)} = n^{a+o(1)}$.</p>

CC BY-SA 3.0
2012-10-25T23:44:46.330Z
If I understand Levin's algorithm, this only applies to search algorithms. This algorithm would work to invert a function $f$, where $f$ can be computed in time $O(n^{o(a)})$.
David Harris
CC BY-SA 3.0
2012-10-26T13:56:19.593Z
I'm not suggesting using Levin's algorithm itself, just the idea of running all the algorithms $A_k$ in parallel using dovetailing, in such a way that each one is slowed down only by a multiplicative factor.
Yuval Filmus
CC BY-SA 3.0
2012-10-26T18:23:59.443Z
@ Yuval, when you dovetail all the algorithms, then how do you decide which answer to accept? In a search problem, you can test each putative output, but in general this is not possible.
David Harris
CC BY-SA 3.0
2012-10-26T19:19:54.227Z
I accept the first answer that appears. We are given that the algorithms $A_k$ correctly decide $L$.
Yuval Filmus
CC BY-SA 3.0
2012-10-24T05:18:00.727Z
2012-10-24T05:18:00.727Z
Yuval Filmus
<p>The question is similar to the questions about constructive existence of the limit of a sequence of (constructive) objects. Usually if you can uniformly construct those objects (here $M\epsilon$) efficiently enough then you can show the existence of the limit constructively. </p>

<p>For example, assume that we have a TM $N(k,x)$ which runs $M_{|k|^{-1}}$ on $x$ and its running time is $O(n^{a+|k|^{-1}})+O(|k|)$ (here the bounds are also uniform, e.g. something like $O(2^k.n^{a+|k|^{-1}})$ would not work). Then we can combine this uniform simulator with the function $(k,x)\mapsto x$ to obtain the machine $N(x,x)$ that runs in time $O(n^{a+o(1)})$. </p>

<p>PS: $O(n^{a+o(1)})$ is a little bit ambiguous because of nesting of asymptotic notations, I am interpreting it as $n^{a+o(1)}$. Also we need $a$ to be not too small, e.g. at least $1$.</p>

CC BY-SA 3.0
2012-10-20T19:22:46.143Z
2012-10-20T20:14:01.917Z
2012-10-20T20:14:01.917Z
Kaveh
<p>Suppose that, for each $\epsilon &gt; 0$, there is an Turing machine $M_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a + o(1)})$? (Here, the $o(1)$ term is measured in terms of $n$, the input length.) </p>

<p>Does it make a difference if the algorithms $M_{\epsilon}$ are computable, or efficiently computable, in terms of $\epsilon$?</p>

<p>Motivation: in many proofs, it is easier to construct algorithms of time $O(n^{a + \epsilon})$ than the limiting algorithm $O(n^{a + o(1)})$. In particular, you need to bound the constant term in $O(n^{a + \epsilon})$ to pass to the limit $O(n^{a+o(1)})$. It would be nice if there is some general result you can invoke to pass to the limit directly.</p>

<cc.complexity-theory><asymptotics>
Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?
David Harris
# Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?

(Asked by: username_0 on 2012-10-20)

Suppose that, for each $\epsilon > 0$, there is an Turing machine $M\_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a + o(1)})$? (Here, the $o(1)$ term is measured in terms of $n$, the input length.)

Does it make a difference if the algorithms $M\_{\epsilon}$ are computable, or efficiently computable, in terms of $\epsilon$?

Motivation: in many proofs, it is easier to construct algorithms of time $O(n^{a + \epsilon})$ than the limiting algorithm $O(n^{a + o(1)})$. In particular, you need to bound the constant term in $O(n^{a + \epsilon})$ to pass to the limit $O(n^{a+o(1)})$. It would be nice if there is some general result you can invoke to pass to the limit directly.

**Tags:** cc.complexity-theory, asymptotics

---

## 2 answers

### Answer by username_2 on 2012-10-20. Score: 10

The question is similar to the questions about constructive existence of the limit of a sequence of (constructive) objects. Usually if you can uniformly construct those objects (here $M\epsilon$) efficiently enough then you can show the existence of the limit constructively.

For example, assume that we have a TM $N(k,x)$ which runs $M\_{|k|^{-1}}$ on $x$ and its running time is $O(n^{a+|k|^{-1}})+O(|k|)$ (here the bounds are also uniform, e.g. something like $O(2^k.n^{a+|k|^{-1}})$ would not work). Then we can combine this uniform simulator with the function $(k,x)\mapsto x$ to obtain the machine $N(x,x)$ that runs in time $O(n^{a+o(1)})$.

PS: $O(n^{a+o(1)})$ is a little bit ambiguous because of nesting of asymptotic notations, I am interpreting it as $n^{a+o(1)}$. Also we need $a$ to be not too small, e.g. at least $1$.


---

### Answer by username_1 on 2012-10-24. Score: 8

You can use Levin's universal search algorithm. Suppose that you can somehow enumerate a sequence of algorithms $A\_k$ deciding $L$, each running in time $C\_k n^{a+1/k}$. Levin's algorithm runs in time $T(n) \leq D\_k n^{a+1/k}$ for every $k$, where $D\_k$ is a constant depending on $C\_k$. So for every $k$,
$$ \tau(n) \triangleq \frac{\log T(n)}{\log n} - a \leq \frac{\log D\_k + (a+1/k) \log n}{\log n} - a = \frac{\log D\_k}{\log n} + \frac{1}{k}. $$
Given $\epsilon>0$, choose $k = \lceil 2/\epsilon \rceil$, and let $N = \lceil D\_k^{2/\epsilon} \rceil$. Then for $n \geq N$, $\tau(n) \leq \epsilon$. Therefore $\tau(n) \rightarrow 0$, and we get that Levin's algorithm runs in time $n^{a+\tau(n)} = n^{a+o(1)}$.

> **Comments:**
> **username_0**: If I understand Levin's algorithm, this only applies to search algorithms. This algorithm would work to invert a function $f$, where $f$ can be computed in time $O(n^{o(a)})$.  
> **username_1**: I'm not suggesting using Levin's algorithm itself, just the idea of running all the algorithms $A_k$ in parallel using dovetailing, in such a way that each one is slowed down only by a multiplicative factor.  
> **username_0**: @ Yuval, when you dovetail all the algorithms, then how do you decide which answer to accept? In a search problem, you can test each putative output, but in general this is not possible.  
> **username_1**: I accept the first answer that appears. We are given that the algorithms $A_k$ correctly decide $L$.  

---

