Bahasa non-reguler mana yang ada dalam

Sebagai contoh, saya tahu bahwa bahasa non-reguler adalah dalam . Saya ingin tahu lebih banyak contoh seperti ini. $a^nb^n$ $AC^0$

complexity-theory regular-languages circuits Alex Grilo
sumber

Palindrom (

)

{w w^{R}}

$\{w w^R\}$

Vor

Apa itu

A C^{0}

$AC^0$

vonbrand

@vonbrand,

adalah kelas sirkuit kedalaman konstan yang berisi dan / atau gerbang tanpa kipas. Yaitu, setiap gerbang dalam suatu sirkuit adalah gerbang "dan" atau "atau", dan memungkinkan sejumlah input yang tidak terbatas masuk.

A C^{0}

$AC^0$

Nicholas Mancuso

Jawaban:

$AC^0$

$AC^0$ $\{a^n b^n c^n\}$
$AC^0$
$AC^0$ $2n$ $n+1$ $AC^0$
$\{w x: |w|=2^n, |x|=n, w[x] = 1\}$ $AC^0$

$2^n+n$ $2^n$ $n$
$AC^0$

$n$
$AC^0$ $\geq \frac{1}{2}+ \varepsilon$

$AC^0$ $Parity \notin AC^0$

sdcvvc
sumber

A C^{0}

$AC^0$

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

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

A C^{0}

$AC^0$

P / p o l y

$P/poly$

@ PålGD, itu tercantum dalam teks Arora dan Barak.

Nicholas Mancuso

Apakah Anda memiliki referensi untuk bukti bahwa multiplexing ada di AC0?

Alex Grilo

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

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