Czy istnieją niekonstruktywne dowody na istnienie „małych” maszyn Turinga / NFA?

Po przeczytaniu powiązanego pytania dotyczącego niekonstruktywnych dowodów istnienia algorytmów, zastanawiałem się, czy istnieją metody pokazania istnienia „małych” (powiedzmy, stanowych) maszyn obliczeniowych bez ich budowania.

Formalnie:

załóżmy, że otrzymaliśmy język i naprawiliśmy jakiś model obliczeniowy (NFA / maszyna Turinga itp.). $L\subseteq \Sigma^*$

Czy istnieją jakieś niekonstruktywne wyniki istnienia pokazujące, że stanowa maszyna dla istnieje, ale bez możliwości jej znalezienia (w czasie )? $n$ $L$ $poly(n,|\Sigma|)$

Na przykład, czy jest jakiś zwykły język dla którego możemy pokazać ale nie wiemy, jak zbudować automat stanowy? $L$ $nsc(L)\leq n$ $n$

( jest niedeterministyczną złożonością stanu , tj. liczbą stanów w minimalnym NFA, które akceptuje ). $nsc(L)$ $L$ $L$

EDYCJA: po dyskusji z Marzio (dzięki!) Myślę, że lepiej sformułować pytanie w następujący sposób:

Czy istnieje język i model obliczeniowy, dla którego obowiązuje: $L$

Wiemy, jak zbudować maszynę obliczającą która ma stanów. $L$ $m$

Mamy dowód, że stanowa maszyna dla istnieje (gdzie ), ale albo w ogóle jej nie możemy znaleźć, albo jej obliczenie zajęłoby wykładniczo czas. $n$ $L$ $n << m$

co to jest nsc (L)? pytanie wydaje się dotyczyć kompresji / złożoności Kołmogorowa, która wymaga znalezienia małych (est) maszyn do reprezentowania ciągów ...

wer 16'14

nsc (L) to niedeterministyczna złożoność stanu L (liczba stanów w najmniejszym NFA, który akceptuje L).

inny pomysł / kąt, może istnieją jakieś „małe” klasy obwodów (inny model obliczeniowy), dla których udowodniono, że potrafią obliczyć pewne funkcje, ale faktyczna konstrukcja jest trudna? SJ niedawno wspomniał Barrington, że programy rozgałęziające o szerokości 5 mogą obliczyć większość ...?

dniu

@vzn Dowód twierdzenia Barringtona daje łatwą procedurę konwersji formuł na programy rozgałęziające.

Sasho Nikolov

@RB: ok, można znaleźć bardziej interesujące przykłady złożoności Kołmogorowa związanej z zasobami (w szczególności złożoności związanej z czasem). Na przykład, biorąc pod uwagę ciąg , jaka jest najmniejsza maszyna działająca w czasie która wypisuje ? W tym przypadku możemy łatwo zbudować bazę TM, która drukuje , ale znalezienie najmniejszej wymaga skanowania wszystkich baz(czas sprawia, że jest obliczalny). Kiedy będę miał więcej czasu, rozwinę moją odpowiedź.

x

$x$

O (2^{n})

$O(2^n)$

x

$x$

x

$x$

| M | < | x |

$|M|<|x|$

Marzio De Biasi

Odpowiedzi:

Tylko rozszerzony komentarz z trywialnym przykładem; możesz wybrać język jednoelementowy:

L_{k} = {M ∣ σ (M) = Σ (k)}

$L_k = \{ M \mid \sigma(M) = \Sigma(k) \}$

tzn. zawiera pierwszą (w porządku leksykograficznym) zajętą maszynę bobra Turinga o rozmiarze (maszyna Turinga o wielkości która po zatrzymaniu osiąga największą liczbę 1 na swojej taśmie). $L_k$ $k$ $k$

Dla każdego język jest regularny ... ale nie mamy pojęcia, jak zbudować mały DFA, który go rozpoznaje (chociaż ma tylko ) :-) $k$ $L_k$ $\leq 2*k(\log k+2)$

Marzio De Biasi
źródło

Chociaż zgadzam się, że to działa, szukałem istnienia pokazującego techniki dla wyraźnie określonego języka L.

Co to jest „jawnie podany język”?

Jeffε

Język (dla pewnej liczby pierwszej ) może zostać rozpoznany przez automatyczny kwantowy automat skończony o stanie QFA), ale dowód nie jest konstruktywny. $\mathtt{MOD_p} = \{a^{ip} \mid i \geq 0\}$ $p$ $O(\log p)$

Najbardziej znaną konstrukcyjnie uzyskaną liczbą stanów jest dla QFA z błędem ograniczonym rozpoznającym . $O(\log^{2+o(1)}p)$ $\mathtt{MOD_p}$

ODNIESIENIE : sekcja 4.2 (Ambainis i Yakaryilmaz, 2015) .

Abuzer Yakaryilmaz
źródło

Innym rozwiązaniem jest użycie lematu Higmana :

Język zamknięty pod słowami jest regularny.

Z pod słowem jeśli możemy uzyskać poprzez usunięcie jakiejś litery w . $u$ $v$ $u$ $v$

Weźmy więc dowolny język L, jego zamknięcie pod słowem jest regularne, ale w ogóle nie jest możliwe do zbudowania, ponieważ L jest arbitralne.

CP
źródło