Czy ?

Oczekuję, że odpowiedź brzmi „nie”, ale tak naprawdę nie mogłem skonstruować kontrprzykładu. Różnica polega na tym, że w $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$ możemy nie być w stanie wybrać algorytmu $O(n^{2+ε})$ równomiernie w $ε$ .

Za pomocą argumentu „jaskółczy ogon” (na przykład patrz to pytanie ), jeśli istnieje zestaw maszyn Turinga $M_i$ decydujących o języku $L$ takim, że $∀ε>0 ∃M_i ∈ O(n^{2+ε})$ , to $L$ jest in $\mathrm{DTIME}(n^{2+o(1)})$ .

Biorąc pod uwagę maszynę Turinga, to czy maszyna działa w czasie $n^{2+o(1)}$ jest $Π^0_3$ . Czy język (podany kod dla maszyny go rozpoznającej) znajduje się w $\mathrm{DTIME}(n^{2+o(1)})$ to $Σ^0_4$ (i $Π^0_3$ ); czy język jest w $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$ jest $Π^0_3$ . Jeśli możemy udowodnić $Σ^0_4$ kompletność (lub po prostu $Σ^0_3$ twardość) $\mathrm{DTIME}(n^{2+o(1)})$ , to rozwiązałoby problem, ale nie jestem pewien, jak to zrobić że.

Problem zostałby również rozwiązany, jeśli znajdziemy sekwencję języków $L_i$ taką, że
* $L_i$ ma naturalny algorytm decyzyjny $O(n^{2+1/i})$ (jednolicie w $i$ ).
* Każde $L_i$ jest skończone.
* Jest nie tylko wielkość $L_i$ nierozstrzygalnym, ale algorytm nie można wykluczyć $w∈L_i$ znacznie szybciej niż $O(n^{2+1/i})$ (w najgorszym przypadku $w$ ), z wyjątkiem skończenie wielu $i$ (w zależności od algorytm).

Jestem również ciekawy, czy istnieją jakieś znaczące / interesujące przykłady (dla $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) \setminus \mathrm{DTIME}(n^{2+o(1)})$ lub analogiczna relacja).

Oto kontrprzykład, tj. Język z algorytmem (przy użyciu wielowarstwowych maszyn Turinga) dla każdego , ale niejednolicie w : Zaakceptuj iff a ta maszyna Turinga zatrzymuje się w mniej niż krokach na pustym wejściu. Inne ciągi znaków są odrzucane.$O(n^{2+ε})$$ε>0$$ε$
$0^k 1^m$$k>0$$k$$m^{2+1/k}$

Dla każdego otrzymujemy algorytm poprzez zakodowanie na sztywno wszystkich wystarczająco małych niehamujących maszyn i symulację reszty.$ε$$O(n^{2+ε})$

Teraz rozważ maszynę Turinga decydującą o języku.$M$

Niech (na pustym wejściu) będzie wydajną implementacją: dla 1,2,4,8, ...:      użyj aby zdecydować, czy zatrzyma się w kroki.      halt iff mówi, że nie zatrzymujemy się, ale nadal możemy zatrzymać się w krokach .$M'$
$n$
$M$$M'$$<n^{2+1/M'}$
$M$$<n^{2+1/M'}$

Dzięki poprawności , nie zatrzymuje się, ale przyjmuje -stepów na wejściu dla nieskończenie wielu . (Jeśli jest zbyt szybki, wówczas byłoby sprzeczne z M. Ograniczenie Ω ( n 2 + 1 / M ' ) zależy od M ' symulującego M w czasie liniowym i poza tym wydajnego.)$M$$M'$$M$$Ω(n^{2+1/M'})$$0^{M'} 1^{n-M'}$$n$$M$$M'$$M$$Ω(n^{2+1/M'})$$M'$$M$