Memutuskan kekosongan persimpangan bahasa reguler dalam waktu subquadratic

Misalkan menjadi dua bahasa reguler yang diberikan oleh NFA sebagai input.M 1 , M $L_1,L_2$$M_1,M_2$

Asumsikan kami ingin memeriksa apakah . Ini jelas dapat dilakukan oleh algoritma kuadratik yang menghitung otomat produk , tetapi saya bertanya-tanya apakah ada yang lebih efisien diketahui.M 1 , M $L_1\cap L_2\neq \emptyset$$M_1,M_2$

Apakah ada algoritma untuk memutuskan apakah ? Apa algoritma yang paling cepat diketahui?L 1 ∩ L 2 ≠ $o(n^2)$$L_1\cap L_2\neq \emptyset$

Jawaban sederhana : Jika memang ada algoritma yang lebih efisien yang berjalan dalam waktu untuk beberapa δ < 2 , maka hipotesis waktu eksponensial yang kuat akan ditolak.$O(n^{\delta})$$\delta < 2$

Kami akan membuktikan teorema yang lebih kuat dan kemudian jawaban sederhana akan mengikuti.

Teorema : Jika kita dapat menyelesaikan masalah non-kekosongan simpang untuk dua DFA dalam waktu , maka setiap masalah yang dipecahkan secara non-deterministik hanya dengan menggunakan n bit memori dapat dipecahkan secara deterministik dalam p o l y ( n ) ⋅ 2 ( δ n / 2 ) waktu.$O(n^{\delta})$$poly(n)\cdot2^{(\delta n/2)}$

Pembenaran : Misalkan kita bisa menyelesaikan persimpangan non-kekosongan untuk dua DFA dalam waktu . Biarkan mesin Turing non-deterministik M dengan tape input hanya baca dan tape kerja biner baca / tulis diberikan. Biarkan string input x panjang n diberikan. Misalkan M tidak mengakses lebih dari n bit memori pada pita kerja biner.$O(n^{\delta})$

Perhitungan M pada input x dapat diwakili oleh daftar konfigurasi yang terbatas. Setiap konfigurasi terdiri dari keadaan, posisi pada pita input, posisi pada pita kerja, dan hingga n bit memori yang mewakili pita kerja.

Sekarang, pertimbangkan bahwa rekaman kerja itu terbelah dua. Dengan kata lain, kita memiliki bagian kiri sel dan bagian kanan$\frac{n}{2}$ sel. Setiap konfigurasi dapat dipecah menjadi bagian kiri dan bagian kanan. Bagian kiri terdiri dari keadaan, posisi pada pita input, posisi pada pita kerja, dan$\frac{n}{2}$ bit dari bagian kiri. Bagian kanan terdiri dari keadaan, posisi pada pita input, posisi pada pita kerja, dan$\frac{n}{2}$ bit dari bagian kanan.$\frac{n}{2}$

Sekarang, kita membangun DFA yang menyatakan bagian kiri dan DFA D 2 yang menyatakan bagian kanan. Karakter alfabet adalah instruksi yang mengatakan ke negara mana harus pergi, bagaimana kepala pita harus bergerak, dan bagaimana sel aktif pita kerja harus dimanipulasi.$D_1$$D_2$

Idenya adalah bahwa dan D 2 membaca dalam daftar instruksi yang sesuai dengan perhitungan M pada input x dan bersama-sama memverifikasi bahwa itu adalah sah dan menerima. Baik D 1 maupun D 2 akan selalu sepakat di mana letak kepala tape karena informasi tersebut dimasukkan dalam karakter input mereka. Oleh karena itu, kita dapat memiliki D 1 memverifikasi bahwa instruksi yang tepat ketika posisi pita kerja di bagian kiri dan D 2 memverifikasi ketika di bagian kanan.$D_1$$D_2$$D_1$$D_2$$D_1$$D_2$

Secara total, terdapat paling banyak status untuk setiap DFA dan paling banyak p o l y ( n ) karakter alfabet yang berbeda.$poly(n) \cdot 2^{n/2}$$poly(n)$

Dengan asumsi awal, berarti kita dapat memecahkan persimpangan non-kekosongan selama dua DFA di waktu.$poly(n) \cdot 2^{(\delta n /2)}$

Anda mungkin menemukan ini membantu: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

CNF-SAT dapat dipecahkan menggunakan bit memori di mana k adalah jumlah variabel. Konstruksi sebelumnya dapat digunakan untuk menunjukkan bahwa jika kita dapat menyelesaikan persimpangan non-kekosongan untuk dua DFA dalam waktu O ( n δ ) , maka kita dapat menyelesaikan CNF-SAT dalam p o l y ( n ) ⋅ 2 ( δ k / 2 ) waktu. Karena itu, jawaban sederhana tetap berlaku.$k+O(\log(n))$$O(n^{\delta})$$poly(n) \cdot 2^{(\delta k/2)}$

Komentar, koreksi, saran, dan pertanyaan disambut. :)