Dalam keadaan apa algoritma

Misalkan, untuk setiap $\epsilon > 0$ , ada mesin Turing $M_{\epsilon}$ yang menentukan bahasa $L$ dalam waktu $O(n^{a + \epsilon})$ . Apakah ada algoritma tunggal yang menentukan $L$ dalam waktu $O(n^{a + o(1)})$ ? (Di sini, istilah $o(1)$ diukur dengan $n$ , panjang input.)

Apakah itu membuat perbedaan jika algoritma $M_{\epsilon}$ yang dihitung, atau secara efisien dihitung, dalam hal $\epsilon$ ?

Motivasi: dalam banyak bukti, lebih mudah untuk membangun algoritma waktu $O(n^{a + \epsilon})$ daripada algoritma pembatas $O(n^{a + o(1)})$ . Secara khusus, Anda perlu mengikat suku konstan dalam $O(n^{a + \epsilon})$ untuk melewati batas $O(n^{a+o(1)})$ . Alangkah baiknya jika ada beberapa hasil umum yang bisa Anda panggil untuk langsung ke batas.

Pertanyaannya mirip dengan pertanyaan tentang keberadaan konstruktif dari batas urutan objek (konstruktif). Biasanya jika Anda dapat secara seragam membangun objek-objek itu (di sini ) cukup efisien maka Anda dapat menunjukkan keberadaan batas secara konstruktif.$M\epsilon$

Misalnya, asumsikan bahwa kita memiliki TM yang menjalankan M | k | - 1 pada x dan waktu operasinya adalah O ( n a + | k | - 1 ) + O ( | k | ) (di sini batas-batasnya juga seragam, misalnya sesuatu seperti 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}})$tidak akan bekerja). Kemudian kita dapat menggabungkan simulator seragam ini dengan fungsi untuk mendapatkan mesin N ( x , x ) yang berjalan dalam waktu O ( n a + o ( 1 ) ) .$(k,x)\mapsto x$$N(x,x)$$O(n^{a+o(1)})$

PS: agak ambigu karena bersarang dari notasi asimptotik, saya menafsirkannya sebagai n a + o ( 1 ) . Kita juga perlu a agar tidak terlalu kecil, misalnya setidaknya 1 .$O(n^{a+o(1)})$$n^{a+o(1)}$$a$$1$

Anda dapat menggunakan algoritma pencarian universal Levin. Misalkan Anda entah bagaimana dapat menghitung urutan algoritma memutuskan L , masing-masing berjalan dalam waktu C k n a + 1 / k . Algoritma Levin berjalan dalam waktu T ( n ) ≤ D k n a + 1 / k untuk setiap k , di mana D k adalah konstanta tergantung pada C k . Jadi untuk setiap 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)}$.