W jakich okolicznościach algorytmy

Załóżmy, że dla każdego istnieje maszyna Turinga M ϵ, która decyduje o języku L w czasie O ( n a + ϵ ) . Czy istnieje jeden algorytm decydujący o L w czasie O ( n a + o ( 1 ) ) ? (Tutaj składnik o ( 1 ) jest mierzony jako n , długość wejściowa.)$\epsilon > 0$$M_{\epsilon}$$L$$O(n^{a + \epsilon})$$L$$O(n^{a + o(1)})$$o(1)$$n$

Czy robi to różnicę, jeśli algorytmy są obliczalne lub wydajnie obliczalne pod względem ϵ ?$M_{\epsilon}$$\epsilon$

Motywacja: w wielu dowodach łatwiej jest zbudować algorytmy czasu niż algorytm ograniczający O ( n a + o ( 1 ) ) . W szczególności musisz związać stały wyraz w O ( n a + ϵ ), aby przejść do granicy O ( n a + o ( 1 ) ) . Byłoby miło, gdyby był jakiś ogólny wynik, który można wywołać, aby przejść bezpośrednio do limitu.$O(n^{a + \epsilon})$$O(n^{a + o(1)})$$O(n^{a + \epsilon})$$O(n^{a+o(1)})$

Pytanie jest podobne do pytań o konstruktywne istnienie granicy sekwencji (konstruktywnych) obiektów. Zwykle, jeśli potrafisz wystarczająco jednolicie konstruować te obiekty (tutaj ) wystarczająco skutecznie, możesz konstruktywnie pokazać istnienie limitu.$M\epsilon$

Załóżmy na przykład, że mamy TM która uruchamia M | k | - 1 na x, a jego czas działania wynosi O ( n a + | k | - 1 ) + O ( | k | ) (tutaj granice są również jednolite, np. Coś w rodzaju O ( 2 k . N a + | k | - 1$N(k,x)$$M_{|k|^{-1}}$$x$$O(n^{a+|k|^{-1}})+O(|k|)$$O(2^k.n^{a+|k|^{-1}})$ nie działałoby) Następnie możemy połączyć ten jednolity symulator z funkcją aby uzyskać maszynę N ( x , x ), która działa w czasie O ( n a + o ( 1 )$(k,x)\mapsto x$$N(x,x)$$O(n^{a+o(1)})$ .

PS: jest trochę niejednoznaczny z powodu zagnieżdżania notacji asymptotycznych, interpretuję to jako n a + o ( 1 ) . Musimy też nie być za mały, np. Przynajmniej$O(n^{a+o(1)})$$n^{a+o(1)}$$a$ .$1$

Możesz użyć uniwersalnego algorytmu wyszukiwania Levina. Załóżmy, że można w jakiś sposób wyliczyć sekwencję algorytmów decydujących o L , z których każdy działa w czasie C k n a + 1 / k . Algorytm Levina działa w czasie T ( n ) ≤ D k n a + 1 / k dla każdego k , gdzie D k jest stałą zależną od C k . Tak więc dla każdego k , τ ( n ) $A_k$$L$$C_k n^{a+1/k}$$T(n) \leq D_k n^{a+1/k}$$k$$D_k$$C_k$$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)}$.