15
$\begingroup$

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

$\endgroup$
  • $\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$ – Michael Wehar Sep 17 '17 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$ – Dmytro Taranovsky Sep 17 '17 at 8:26
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand the last sentence. Where do we get lower bounds on the running time of $M$? $\endgroup$ – Emil Jeřábek Sep 17 '17 at 7:34
  • $\begingroup$ @EmilJeřábek I clarified the answer. Let me know if it can be improved further. $\endgroup$ – Dmytro Taranovsky Sep 17 '17 at 8:16
  • 1
    $\begingroup$ Pethaps I don't understand what "but we can still halt in..." means. What, exactly, does M' do? $\endgroup$ – Emil Jeřábek Sep 17 '17 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$ – Dmytro Taranovsky Sep 17 '17 at 10:49
  • $\begingroup$ Ok, I think I figured it out. Thank you. $\endgroup$ – Emil Jeřábek Sep 18 '17 at 21:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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