16
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)})$. $\endgroup$ – David Harris Oct 25 '12 at 23:44
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 26 '12 at 13:56
  • $\begingroup$ @ 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. $\endgroup$ – David Harris Oct 26 '12 at 18:23
  • $\begingroup$ I accept the first answer that appears. We are given that the algorithms $A_k$ correctly decide $L$. $\endgroup$ – Yuval Filmus Oct 26 '12 at 19:19

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.