2FA złożoność stanu k-Clique?

W prostej formie:

Można dwukierunkowa skończony automat rozpoznaje $v$ wykresy -Vertex które zawierają trójkąt z $o(v^3)$ stany?

Detale

Zainteresowania są tu $v$ wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki $\{0,1,\dots,v-1\}$ .

Załóżmy, że $(M_v)$ jest ciągiem dwukierunkowy automaty skończone (deterministyczny lub niedeterministyczny), tak że $M_v$ rozpoznaje $k$ -Clique na $v$ wykresach wejściowych -Vertex i ma $s(v)$ stany. Ogólna forma pytania brzmi: czy $s(v) = \Omega(v^k)$ ?

Jeśli $k = k(v) = \omega(1)$ i $s(v) \ge v^{k(v)}$ dla nieskończenie wielu $v$ , to NL ≠ NP. Mniej ambitnie, dlatego zastrzegam, że $k$ jest ustalone, a przypadek $k=3$ jest pierwszym nietrywialnym.

tło

Dwukierunkowy automat skończony (2FA) to maszyna Turinga, która nie ma obszaru roboczego, tylko stałą liczbę stanów wewnętrznych, ale może przesuwać swoją głowicę wejściową tylko do odczytu tam iz powrotem. W przeciwieństwie do tego zwykły automat skończony (1FA) przesuwa głowicę wejściową tylko do odczytu w jednym kierunku. Automaty skończone mogą być deterministyczne (DFA) lub niedeterministyczne (NFA), a także mieć jedno- lub dwukierunkowy dostęp do swoich danych wejściowych.

Właściwość wykresu jest podzbiorem wykresów. Niech oznaczamy wykresach -Vertex z nieruchomości . Dla każdej właściwości wykresu język może być rozpoznany przez 1DFA z maksymalnie stanami , poprzez użycie stanu dla każdego możliwego wykresu i oznaczenie go zgodnie z , oraz przejścia między stanami oznaczone po krawędziach. jest zatem zwykłym językiem dla dowolnej właściwości $Q$ $Q_v$ $v$ $Q$ $Q$ $Q_v$ $2^{v(v-1)/2}$ $Q$ $Q_v$ $Q$ . Według twierdzenia Myhill-Nerode istnieje unikalny aż do izomorfizmu najmniejszy 1DFA, który rozpoznaje . Jeśli ma to stany , wówczas standardowe granice wysadzenia dają, że 2FA rozpoznające ma co najmniej stany . To podejście poprzez standardowe granice wysadzenia daje co najwyżej kwadratową in dolną granicę liczby stanów w 2FA dla dowolnego (nawet gdy jest trudne lub nierozstrzygalne). $Q_v$ $2^{s(v)}$ $Q_v$ $s(v)^{\Omega(1)}$ $v$ $Q_v$ $Q$

-Clique to właściwość graph zawierająca pełnypodgraph -vertex. Rozpoznawanie kliki może być wykonane przez 1NFA, który najpierw nie deterministycznie wybiera jedną z $k$ $k$ $k$ $_v$ różne potencjalnekliki, których należy szukać, a następnie skanuje dane wejściowe raz, szukając każdej z wymaganych krawędzi w celu potwierdzenia kliki i śledząc te krawędzie za pomocąstanówdla każdego z różne potencjalne kliky. Taki 1NFA ma $\binom{v}{k}$ $k$ $2^{k(k-1)/2}$ Zjednoczonych, gdzie. Kiedyjest ustalone, są tostany. Zezwolenie na dwukierunkowy dostęp do danych wejściowych potencjalnie umożliwia poprawę w stosunku do tego jednokierunkowego ograniczenia. Pytanie dotyczy zatem $\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$ $1 \le c_v \le e$ $k$ $\Theta(v^k)$ $k=3$ czy 2FA może zrobić lepiej niż ta górna granica 1FA.

Dodatek (16.04.2017): patrz także powiązane pytanie dotyczące deterministycznego czasu i ładna odpowiedź obejmująca najbardziej znane algorytmy . Moje pytanie dotyczy niejednolitej, niedeterministycznej przestrzeni. W tym kontekście redukcja do mnożenia macierzy stosowana przez algorytmy efektywne czasowo jest gorsza niż metoda brutalnej siły.

— András Salamon
źródło

Naprawdę lubię te pytania! Dziękujemy za udostępnienie! :)

— Michael Wehar,

Wydaje mi się, że trójkąty mogą być wykonane przez 2FA ze stanem (n jest liczbą wierzchołków). $A$ $O(n^2)$

Dla idea jest następująca: $k=3$

W fazie 1 wybiera krawędź i przechowuje w swoim stanie $A$ $(i,j)$ $(phase 1,i,j)$
W fazie 2 przesuwa się do jakiejś krawędzi formy lub i przyjmuje stan formy $(i,m)$ $(m,i)$ $(phase 2,j,m)$
W fazie 3 sprawdza, czy istnieje jakieś zbocze lub i przyjmuje stan akceptacji, jeśli go znajdzie. $(j,m)$ $(m,j)$

Można to właściwie zrobić prawie od lewej do prawej (wtedy może niedeterministycznie zdecydować się na lub w fazie 2). Jeśli jednak druga krawędź ma postać , musi najpierw odczytać a następnie , tj. Potrzebny jest tutaj pojedynczy lewy krok. $A$ $(j,m)$ $(m,j)$ $(m,i)$ $A$ $i$ $m$

To powinno dać automaty ze stanami dla Kliki dla , najpierw zgadując zbiór o wielkości i testując, że węzły są połączone parami krawędziami i dla każdego I, J, m powyżej, sprawdzając, czy mają one krawędzie do wszystkich węzłów . $O(n^{k-1})$ $k$ $k>3$ $S$ $k-3$ $S$ $S$

— Thomas S.
źródło

Nie rozumiem, jak to jest

? Śledzone są trzy wierzchołki

O (n^{2})

$O(n^2)$

i, j, m

$i,j,m$

— András Salamon

Tylko dwa na raz. Odczyt

w fazie 2 odbywa się w dwóch przejściach. Po odczytaniu

zasadniczo przechodzi od (faza 1, i, j) do (faza 1a, i, j) (wskazując, że właśnie zobaczył

), aw następnym kroku do (faza 2, j, m). W tym momencie robi się to za pomocą

, ponieważ już widział

i tylko

musi być sprawdzone.

(i, m)

$(i,m)$

i

$i$

A

$A$

i

$i$

i

$i$

(i, j)

$(i,j)$

(i, m)

$(i,m)$

(j, m)

$(j,m)$

— Thomas S

Jeśli liczba krawędzi i wierzchołków jest w przybliżeniu taka sama, myślę, że to działa dobrze, ale interesującym przypadkiem jest, gdy

. Innymi słowy, myślę, że twoje podejście wykorzystuje przynajmniej

stany.

e = Ω (v^{2})

$e = \Omega(v^2)$

v \cdot e

$v \cdot e$

— Michael Wehar,

Myślę, że masz rację. Jeśli dane wejściowe są podane w dobrym formacie, to działa. :)

— Michael Wehar,

@Marzio: nie, mówi (nie, mówi deterministyczny lub niedeterministyczny)

— Thomas S