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$

cc.complexity-theory automata-theory turing-machines

— RB
źródło

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).

— RB

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.

— RB

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