Kesenjangan besar antara RAM dan kompleksitas mesin Turing

Jika kita hanya mempertimbangkan masalah dalam P, apakah ada celah besar antara algoritma kata-RAM yang paling cepat diketahui dan algoritma mesin Turing yang paling cepat diketahui untuk masalah tertentu? Saya sangat tertarik jika ada celah lebar untuk masalah alam yang menjadi perhatian umum.

Diketahui bahwa setiap masalah yang dapat Anda hitung pada mesin RAM dalam waktu , Anda dapat melakukannya dalam Mesin Turing paling lama dalam waktu . Anda perlu memperhatikan bahwa ukuran total memori yang digunakan tidak boleh lebih dari , karena itu berarti Anda melakukan lebih banyak operasi tulis daripada , jadi setiap kali Anda mengambil sesuatu dari memori RAM, Turing mesin akan mengambil dalam kasus terburuk waktu untuk menemukan elemen yang diinginkan secara berurutan dari rekaman itu. Selain akses memori, sisa operasi harus memakan waktu yang bersamaan. Dan dengan demikian Anda mendapatkan terikat.T ( n ) 2 T ( n ) T ( n ) T ( n $T(n)$$T(n)^2$$T(n)$$T(n)$$T(n)$

Contoh di bawah ini membuktikan bahwa algoritma yang membutuhkan untuk menyelesaikan masalah pada kata-Ram mungkin membutuhkan pada Mesin Turing 1-tape (TM) ) yang persis mengeksekusi semua perhitungan ditunjukkan oleh . Saya mengerti pertanyaan terkait dengan 1-tape TM, dan saya hanya menggunakan yang ini sebagai jawaban saya. Ini adalah suntingan untuk menanggapi pernyataan Emil Jeřábek.O ( n log ( n ) ) O ( n 2 log ( n ) 3 ) A$A$$O(n\log(n))$$O(n^2 \log(n)^3)$$A$

Kami akan menemukan kesimpulan yang lebih umum berikut . Untuk membuktikan bahwa TM dapat menyelesaikan dalam masalah yang diselesaikan dalam dengan algoritma pada RAM, tidak cukup menjalankan pada TM. Sebuah pintar algoritma mungkin diperlukan. Hal yang sama berlaku jika seseorang ingin membuktikan overhead . Membuktikan keberadaan algoritma yang pintar kapan pun dibutuhkan tampaknya jauh dari langsung, untuk sedikitnya. Ini tidak sejalan dengan tanggapan lain yang pada dasarnya hanya mengusulkan untuk mensimulasikan / mengeksekusi pada TM semua perhitungan RAM (dari algoritma ) untuk mengumumkan kompleksitas TM seperti$O(T(n)^2)$$O(T(n))$$A$$A$$O(n\log(n))$$A$$O(T(n)^2)$ atau .$O(T(n)n\log(n))$

Masalah: Kami diberi array / tabel dengan bilangan bulat yang masing-masing disimpan di bit. Kita diberi array kedua dengan posisi , masing-masing merekam sejumlah bit. Untuk setiap , kami mendefinisikan jika MOD MOD . Kalau tidak, . Keluaran . Saya menganggap input diberikan sebagai rekaman dengan$\texttt{tab}$$n=2k$$\log(n)$$\texttt{d}$$\log(n)$$\log(n)$$t\in[0..\log(n)-1]$$X_t=1$$\texttt{tab}[i]$$\texttt{d}[t]=\texttt{tab}[n/2+i]$$\texttt{d}[t]~\forall i\in [0..n/2-1]$$X_t=0$$\sum_{t=0}^{\log(n)-1} X_t$$n\log(n)+\log(n)\log(n)$ digit biner, untuk menanggapi komentar Emil Jeřábek.

Algoritma pada RAM$A$ A RAM dengan ukuran kata membutuhkan = untuk membaca input string biner data. Tetapi setelah membaca data, itu hanya dapat bekerja dengan kata-kata dengan ukuran . Algoritma menghitung di dengan menelusuri semua dan menguji kondisinya. Loop utama adalah UNTUK : menghitung . Kompleksitas totalnya adalah (membaca data) +$w=\log(n)$$O(n\log(n)+\log(n)^2)$$O(n\log(n))$$\log(n)$$A$$X_t$$O(n)$$i\in [0..n/2-1]$$A$$t=0, 1, 2, \dots \log(n)-1$$X_t$$O(n\log(n))$$O(n\log(n))$(melakukan perhitungan), sehingga dapat melakukan semuanya dalam pada RAM.$A$$O(n\log(n))$

Algoritma pada 1-tape TM:$A$ Saya berpendapat bahwa TM satu-tape membutuhkan waktu untuk tetap . Dari sudut pandang TM, menentukan sama dengan menguji kesetaraan dua string biner dengan panjang . Misalnya, operasi MOD MOD mungkin sama dengan menghapus bit dari . Dalam kasus seperti itu, menentukan setara dengan pengujian kesetaraan pada string bit dengan panjang . Diketahui bahwa pengujian kesetaraan dua untaian panjang$O(n^2 \log(n)^2)$$t$$A_t$$O(n\log(n))$$\texttt{tab}[i]$$\texttt{d}[t]$$0$$\texttt{tab}[i]$$A_t$$n(\log(n)-1)/2$$m$membutuhkan pada 1-tape TM, tapi saya tidak bisa menemukan referensi sekarang. Namun, saya memberikan bukti dalam ps. Jika TM mengeksekusi loop utama dari , itu harus menghabiskan setidaknya untuk setiap , berakhir di .$O(m^2)$$A$$O((n\log n)^2)$$t=0, 1, 2, \dots \log(n)-1$$O(n^2 \log(n)^3)$

ps. Saya menunjukkan bahwa pengujian kesetaraan pada string bit dengan bit tidak bisa lebih cepat daripada pengujian palyndrome pada string dengan bit (palyndrome dikenal untuk mengambil setidaknya waktu). Kami dapat memodifikasi algoritma TM apa pun untuk pengujian kesetaraan untuk menyelesaikan palindrome. Asumsikan pengujian-persamaan TM dimulai dengan dua bilangan bulat: satu di kiri kepala, satu di kanan (ini adalah formulir input paling sederhana untuk TM). Setiap gerakan di atas posisi kiri dapat dicerminkan (tercermin) di atas posisi yang tepat. Kami membangun TM cermin: setiap kali TM awal berada di posisi (di sebelah kiri), TM cermin di posisi (di kanan). Jika TM menyelesaikan pengujian kesetaraan dalam waktu kurang dari$m$$m$$O(m^2)$$-x<0$$x$$O(m^2)$, TM cermin yang dimodifikasi ini akan menyelesaikan palindrom dalam waktu kurang dari .$O(m^2)$

Juga, ada beberapa algoritma TM pengujian kesetaraan di luar sana dan semuanya membutuhkan waktu kuadrat karena mereka membutuhkan zig-zag, lihat misalnya Mesin Turing Contoh 2 di courses.cs.washington.edu/courses/cse431/14sp/scribes/ lec3.pdf