Decydowanie o pustce przecięcia zwykłych języków w czasie subkwadratowym

Niech będą dwoma zwykłymi językami podanymi przez NFA M_1 jako dane wejściowe.M 1 , M $L_1,L_2$$M_1,M_2$

Załóżmy, że chcielibyśmy sprawdzić, czy . Można to wyraźnie zrobić za pomocą algorytmu kwadratowego, który oblicza automat produktu , , ale zastanawiałem się, czy wiadomo coś bardziej wydajnego.M 1 , M $L_1\cap L_2\neq \emptyset$$M_1,M_2$

Czy istnieje algorytm do decydowania, czy ? Jaki jest najszybszy znany algorytm?L 1 ∩ L 2 ≠ $o(n^2)$$L_1\cap L_2\neq \emptyset$

Prosta odpowiedź : jeśli istnieje bardziej wydajny algorytm działający w czasie dla pewnego δ < 2 , wówczas hipoteza silnego wykładniczego czasu byłaby obalona.$O(n^{\delta})$$\delta < 2$

Udowodnimy mocniejsze twierdzenie, a następnie pojawi się prosta odpowiedź.

Twierdzenie : Jeśli możemy rozwiązać problem nieopróżnienia przecięcia dla dwóch DFA w czasie , to każdy problem, który nie jest deterministycznie rozwiązany przy użyciu tylko n bitów pamięci, jest deterministycznie rozwiązany w p o l y ( n ) ⋅ 2 Czas ( δ n / 2 ) .$O(n^{\delta})$$poly(n)\cdot2^{(\delta n/2)}$

Uzasadnienie : Załóżmy, że możemy rozwiązać brak pustki skrzyżowania dla dwóch DFA w czasie . Niech zostanie podana niedeterministyczna maszyna Turinga M z taśmą wejściową tylko do odczytu i binarną taśmą roboczą do odczytu / zapisu. Niech zostanie podany ciąg wejściowy x o długości n. Załóżmy, że M nie ma dostępu do więcej niż n bitów pamięci na binarnej taśmie roboczej.$O(n^{\delta})$

Obliczenia M na wejściu x mogą być reprezentowane przez skończoną listę konfiguracji. Każda konfiguracja składa się ze stanu, pozycji na taśmie wejściowej, pozycji na taśmie roboczej i maksymalnie n bitów pamięci reprezentujących taśmę roboczą.

Teraz rozważmy, że taśma robocza została podzielona na pół. Innymi słowy, mamy lewą sekcję komórki i prawa sekcja$\frac{n}{2}$ komórki. Każda konfiguracja może zostać podzielona na lewą i prawą część. Lewy kawałek składa się ze stanu, pozycji na taśmie wejściowej, pozycji na taśmie roboczej oraz$\frac{n}{2}$ bity z lewej sekcji. Właściwy kawałek składa się ze stanu, pozycji na taśmie wejściowej, pozycji na taśmie roboczej oraz$\frac{n}{2}$ bity z prawej sekcji.$\frac{n}{2}$

Teraz budujemy DFA którego stany są lewymi kawałkami, i DFA D 2, których stany są prawymi kawałkami. Znaki alfabetu to instrukcje określające, do którego stanu należy przejść, w jaki sposób powinny się poruszać głowice taśmy oraz jak manipulować aktywną komórką taśmy roboczej.$D_1$$D_2$

Chodzi o to, że i D 2 czytają listę instrukcji odpowiadających obliczeniu M na wejściu x i razem sprawdzają, czy jest poprawna i akceptuje. Zarówno D 1 i D 2 będzie zawsze uzgodnić gdzie głowice są dlatego, że informacje są zawarte w ich znaków wejściowych. Dlatego możemy poprosić D 1 o sprawdzenie, czy instrukcja jest odpowiednia, gdy pozycja taśmy roboczej znajduje się w lewym elemencie, a D 2 o sprawdzenie, czy w prawym elemencie.$D_1$$D_2$$D_1$$D_2$$D_1$$D_2$

W sumie co najwyżej jest dla każdej DFA co najwyżej P ° l r ( n ) oddzielnych liter alfabetu.$poly(n) \cdot 2^{n/2}$$poly(n)$

Przy wstępnym założeniu, wynika, że można rozwiązać przecięcia non-pustkę dla w dwóch DFA czasu.$poly(n) \cdot 2^{(\delta n /2)}$

Może ci się to przydać: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

CNF-SAT można rozwiązać za pomocą bitów pamięci, gdzie k jest liczbą zmiennych. Powyższą konstrukcję można wykorzystać, aby pokazać, że jeśli uda nam się rozwiązać brak pustki przecięcia dla dwóch DFA w czasie O ( n δ ) , to możemy rozwiązać CNF-SAT w p o l y ( n ) ⋅ 2 ( δ k / 2 ) czas. Dlatego prosta odpowiedź jest ważna.$k+O(\log(n))$$O(n^{\delta})$$poly(n) \cdot 2^{(\delta k/2)}$

Komentarze, poprawki, sugestie i pytania są mile widziane. :)