Kwadratowy związek między przestrzenią niedeterministyczną a deterministyczną?

Twierdzenie Savitcha pokazuje, że $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ dla wszystkich wystarczająco dużych funkcji $f$ , i udowodnienie, że jest ciasno, było otwartym problemem od dziesięcioleci .

Załóżmy, że podchodzimy do problemu z drugiego końca. Dla uproszczenia załóżmy logiczny alfabet. Ilość miejsca wykorzystywanego przez TM do decydowania o języku obliczeniowym jest często ściśle związana z logarytmem liczby stanów używanych przez automat symulujący TM dla każdego regularnego wycinka języka. To motywuje następujące pytanie.

Niech $D_n$ będzie liczbą składniowo odrębnych DFA o $n$ stanach, a $N_n$ będzie liczbą różnych NFA o $n$ stanach. Łatwo jest wykazać, że $\lg N_n$ jest zbliżone do $(\lg D_n)^2$ .

Ponadto, niech $D_n'$ będzie liczbą różnych regularnych języków, które mogą być rozpoznane przez DFA ze stanami , i niech będzie liczbą rozpoznawaną przez NFA.$n$$N_n'$

Czy wiadomo, czy jest bliskie ?$\lg N_n'$$(\lg D_n')^2$

Nie jest dla mnie jasne, w jaki sposób i lub i są ze sobą powiązane, ani jak blisko. Jeśli wszystko to odnosi się do dobrze znanego pytania w teorii automatów, to wskazówka lub wskaźnik byłyby mile widziane. To samo pytanie dotyczy również automatów dwukierunkowych z tego samego powodu i jestem szczególnie zainteresowany tą wersją.$D_n$$D_n'$$N_n$$N_n'$

W mojej pracy z Domaratzki i Kisman „O liczbie różnych języków akceptowanych przez skończone automaty z n stanami” opublikowanej w J. Automata, Languages ​​and Combinatorics 7 (2002) udowodniliśmy, że jeśli jest liczbą różne języki akceptowane przez NFA z n stanami nad alfabetem k -liter, a g k ( n ) jest podobnie liczbą różnych języków akceptowanych przez DFA, a następnie dla ustalonego k ≥ $G_k (n)$$n$$k$$g_k (n)$$k \geq 2$

(i) jest asymptotycznie k n log $\log g_k (n)$$kn\log n$

(ii) jest, aż do mniejszych rzędów, asymptotycznie pomiędzy ( k - 1 ) n 2 i k n 2 .$\log G_k (n)$$(k-1)n^2$$kn^2$