Hubungan kuadratik antara ruang nondeterministik dan deterministik?

Teorema Savitch menunjukkan bahwa untuk semua fungsi yang cukup besar , dan membuktikan bahwa ini ketat telah menjadi masalah terbuka selama beberapa dekade. .$\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$$f$

Misalkan kita mendekati masalah dari ujung yang lain. Untuk kesederhanaan, asumsikan alfabet Boolean. Jumlah ruang yang digunakan oleh TM untuk menentukan bahasa yang dapat dihitung sering terkait erat dengan logaritma jumlah negara yang digunakan oleh automaton yang mensimulasikan TM untuk setiap irisan bahasa secara teratur. Ini memotivasi pertanyaan berikut.

Biarkan menjadi jumlah DFA yang berbeda secara sintaksis dengan status , dan biarkan menjadi jumlah NFA berbeda dengan status . Sangat mudah untuk menunjukkan bahwa dekat dengan . n N n n lg N n ( lg D n ) $D_n$$n$$N_n$$n$$\lg N_n$$(\lg D_n)^2$

Selanjutnya, biarkan menjadi jumlah bahasa reguler yang berbeda yang dapat dikenali oleh DFA dengan negara , dan biarkan menjadi nomor yang diakui oleh NFA. n N ′ $D_n'$$n$$N_n'$

Apakah diketahui apakah dekat dengan ? ( lg D ′ n ) $\lg N_n'$$(\lg D_n')^2$

Tidak jelas bagi saya bagaimana dan , atau dan , saling terkait satu sama lain, atau seberapa dekat. Jika semua ini berhubungan dengan pertanyaan terkenal dalam teori automata maka petunjuk atau penunjuk akan dihargai. Pertanyaan yang sama juga relevan untuk automata dua arah, karena alasan yang sama, dan saya sangat tertarik dengan versi ini.$D_n$$D_n'$$N_n$$N_n'$

Dalam makalah saya dengan Domaratzki dan Kisman, "Pada jumlah bahasa berbeda yang diterima oleh automata terbatas dengan n negara" yang diterbitkan dalam J. Automata, Languages, and Combinatorics 7 (2002) kami membuktikan bahwa jika adalah jumlah perbedaan bahasa yang diterima oleh NFA dengan menyatakan lebih dari alfabet , dan juga jumlah bahasa berbeda yang diterima oleh DFA, kemudian untuk tetap$G_k (n)$$n$$k$$g_k (n)$$k \geq 2$

(i) adalah, hingga istilah pesanan yang lebih kecil, secara asimptotik$\log g_k (n)$$kn\log n$

(ii) adalah, hingga istilah pesanan yang lebih kecil, asimtotik antara dan .$\log G_k (n)$$(k-1)n^2$$kn^2$