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. $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. $L_1\cap L_2\neq \emptyset$ $M_1,M_2$

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

— RB
źródło

Jeśli ktoś ma dobre pomysły, daj mi znać, ale obecnie jest to otwarty problem. Jeśli mógłbyś rozwiązać ten problem, powiedzmy w czasie liniowym, to w zasadzie każdy problem rozwiązany przez niedeterministyczną maszynę wykorzystującą tylko n bitów pamięci mógłby zostać rozwiązany deterministycznie w czasie .

2^{\frac{n}{2}}

$2^{\frac{n}{2}}$

— Michael Wehar

Myślę, że wciąż jest dostępny dla każdego subkwadratowego. Więcej informacji: rjlipton.wordpress.com/2009/08/17/…

— Michael Wehar

Na przykład (na podstawie komentarza Michaela), silna hipoteza wykładniczego czasu sugeruje, że wykładnik powinien wynosić 2. Myślę, że może to również wynikać z hipotezy wykładniczego czasu ...

— Ryan Williams

RB: Załóżmy, że możesz przetestować pustkę dwóch DFA o rozmiarze

w czasie

. Teraz, jeśli masz

DFA o rozmiarze

, możesz zbudować iloczyn pierwszych

DFA i pozostałych

DFA. Następnie sprawdź pustkę w czasie

n

$n$

n^{1 + ε}

$n^{1+\varepsilon}$

ε < 1

$\varepsilon < 1$

k

$k$

n

$n$

k / 2

$k/2$

k / 2

$k/2$

co jest lepsze niż

. vzn: Ten wielokrotnie nagradzany artykuł napisał @MichaelWehar, który skomentował ten wątek. Michael, być może mógłbyś udzielić odpowiedzi, jeśli masz czas!

(n^{k / 2})^{1 + ε} = n^{\frac{1}{2} k + \frac{ε}{2} k}

$(n^{k/2})^{1+\varepsilon} = n^{\frac{1}{2}k + \frac{\varepsilon}{2}k}$

n^{k}

$n^k$

— Michael Blondin,

@ RyanWilliams Cześć Ryan, co prowadzi cię do wniosku, że słabsza wykładnicza hipoteza czasowa implikuje, że nie możemy szybciej rozwiązać problemu braku pustki skrzyżowania dla dwóch DFA? Ktoś inny zasugerował mi to raz. :)

— Michael Wehar

Prosta odpowiedź : jeśli istnieje bardziej wydajny algorytm działający w czasie dla pewnego , 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 . $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 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 czytają listę instrukcji odpowiadających obliczeniu M na wejściu x i razem sprawdzają, czy jest poprawna i akceptuje. Zarówno i będzie zawsze uzgodnić gdzie głowice są dlatego, że informacje są zawarte w ich znaków wejściowych. Dlatego możemy poprosić sprawdzenie, czy instrukcja jest odpowiednia, gdy pozycja taśmy roboczej znajduje się w lewym elemencie, a 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 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 , to możemy rozwiązać CNF-SAT w 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. :)

— Michael Wehar
źródło

wszystko świetnie, ale pierwotne pytanie powyżej dotyczyło NFA; czy to wszystko nadal następuje? niektóre kluczowe szczegóły zostały pominięte. wydaje się wart papieru. czy to wszystko w opublikowanym? jeśli tak, proszę przytoczyć je / powiązać z ponumerowanymi twierdzeniami tam itp., pomocne byłoby również wskazanie tego bardziej w kategoriach klas złożoności standardowej L, P, NP, PSpace, ExpTime itp., jeśli to możliwe. zastanawiasz się także, czy można coś powiedzieć o kierunku „silnej” pustki przecięcia DFA w dwóch kierunkach dolnej granicy (

?) → SETH ...? co trzeba na to pokazać?

Ω (n^{2})

$\Omega(n^2)$

— vzn

Cześć VZN, problem przecięcia dla NFA wydaje się nieco trudniejszy niż problem przecięcia dla DFA. Nie dzieje się tak jednak, ponieważ występuje sparametryzowane ograniczenie od braku pustki skrzyżowania dla

NFA do braku pustki skrzyżowania dla

DFA. Jest to wspomniane w mojej pierwszej pracy.

k

$k$

k

$k$

— Michael Wehar

Być może możesz bardziej szczegółowo opisać, co masz na myśli, mówiąc o dwudrożnym DFA. Problem braku pustki dla dwukierunkowych DFA z przewróceniem

jest tak samo trudny jak problem braku pustki przecięcia dla

jednokierunkowych DFA. Link: cs.stackexchange.com/questions/13456/…

(2 k - 2)

$(2k-2)$

k

$k$

— Michael Wehar

W kategoriach standardowych klas złożoności można by to sformułować następująco:

oznacza, że SETH jest fałszem. Kiedy piszę

, mam na myśli

N S p a c e (2 \cdot \log (n)) \subseteq D T i m e (n)

$NSpace(2 \cdot \log(n)) \subseteq DTime(n)$

N S p a c e (2 \cdot \log (n))

$NSpace(2 \cdot \log(n))$

2 \cdot \log (n)

$2\cdot \log(n)$ przestrzeń dla niedeterministycznych maszyn Turinga z dwustronną taśmą wejściową tylko do odczytu i dwustronną taśmą roboczą do odczytu / zapisu binarnego.

— Michael Wehar,