Które języki nieregularne są w

Na przykład wiem, że nieregularny język $a^nb^n$ jest w . Chciałbym poznać więcej takich przykładów. $AC^0$

complexity-theory regular-languages circuits

— Alex Grilo
źródło

Palindromes (

)

{w w^{R}}

$\{w w^R\}$

— Vor

Co to jest

A C^{0}

$AC^0$

— vonbrand

@ vonbrand,

jest klasą obwodów o stałej głębokości, zawierających i / lub bramki niezwiązanego wachlarza. Oznacza to, że każda bramka w obwodzie jest bramką „i” lub „lub” i pozwala na nieograniczoną liczbę wejść.

A C^{0}

$AC^0$

— Nicholas Mancuso

Języki w może być bardziej skomplikowane niż naiwny intuicja może sugerować. $AC^0$

Oczywiście zawiera , który jest nie-context wolne. $AC^0$ $\{a^n b^n c^n\}$
Każdy język jednoargumentowy jest w niejednolitej formie ; na przykład problem zatrzymania wyrażony jednostronnie. $AC^0$
Dodawanie można zaimplementować w za pomocą sumatora przeniesienia. Tutaj wejście ma bitów reprezentujących dwie liczby, a wyjście zawiera przewodów (równoważnie, każdy bit wyjściowy może być zrealizowany w ) $AC^0$ $2n$ $n+1$ $AC^0$
Multipleksowanie: jest w . $\{w x: |w|=2^n, |x|=n, w[x] = 1\}$ $AC^0$

Multiplekser to funkcja na zmiennych, która generuje wartość jednej z zmiennych, gdzie indeks jest określony przez zmiennych. (To samo dotyczy indeksu zapisanego jednostronnie). $2^n+n$ $2^n$ $n$
Obliczenia wzorów 3SAT są w . $AC^0$

Dane wejściowe składają się z zmiennych, po których następują niektóre klauzule, każda zawiera trzy literały, przy czym każda literał jest indeksem zmiennej (jedno lub dwójkowy, nie ma znaczenia) i nieco wskazuje na możliwą negację. Możesz ocenić literały za pomocą multiplekserów, a następnie dodać warstwę OR, a następnie duży AND na wierzchu. $n$
nie zawiera większość, ale nie zawiera w przybliżeniu większość: funkcję, która jest równa większości, jeśli wyjście $AC^0$ zera lub jedynki. Zobacz „Przybliżone zliczanie z jednolitymi obwodami o stałej głębokości” autorstwa Ajtai. $\geq \frac{1}{2}+ \varepsilon$

jest zamknięty pod logicznej operacji, łączenie i kompozycji, aby można było połączyć w przykładach powyżej. Teraz powinieneś poczuć szacunek dla i innych dolnych granic obwodu! $AC^0$ $Parity \notin AC^0$

— sdcvvc
źródło

Czy masz jakieś odniesienia do tego? Zwłaszcza, że jednoargumentowy problem z zatrzymaniem występuje w

. Ponieważ

, nie rozumiem tego (jest późno, gdzie jestem, to może być moja wymówka).

A C^{0}

$AC^0$

A C^{0} \subseteq A C = N C \subseteq P

$AC^0 \subseteq AC = NC \subseteq P$

— Pål GD

To jest niejednolite

(jak

), w którym obwód może dowolnie zmieniać się wraz z długością wejściową.

A C^{0}

$AC^0$

P / p o l y

$P/poly$

— sdcvvc

@ PålGD, jest to określone w tekście Arora i Barak.

— Nicholas Mancuso,

Czy masz odniesienie do dowodu, że multipleksowanie jest w AC0?

— Alex Grilo

@Alex Grilo, niestety nie; Myślę, że to folklor. Po prostu zrób

⋁_{i = 0}^{2^{n} - 1} (x = i \land w [i] = 1)

$\bigvee_{i=0}^{2^n-1} (x=i \wedge w[i]=1)$

— sdcvvc