Biasa versus TC0

Menurut Kompleksitas Kebun Binatang , $\mathsf{Reg} \subseteq \mathsf{NC^1}$ dan kita tahu bahwa $\mathsf{Reg}$ tidak dapat dihitung sehingga $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$ . Namun tidak disebutkan apakah $\mathsf{Reg} \subseteq \mathsf{TC^0}$ atau tidak. Karena kita tidak tahu $\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$ kita juga tidak tahu $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$ .

Apakah ada kandidat untuk masalah dalam yang tidak ada dalam ? $\mathsf{Reg}$ $\mathsf{TC^0}$

Apakah ada hasil kondisional yang menyiratkan bahwa , mis. Jika maka ? $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$ $\mathsf{NC^1} \not\subseteq \mathsf{TC^0}$ $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$

cc.complexity-theory fl.formal-languages automata-theory circuit-complexity regular-language Kaveh
sumber

Jawaban:

Ambil sebagai alfabet dan Barrington membuktikan dalam [2] bahwa adalah -lengkap untuk pengurangan (dan bahkan dengan pengurangan yang lebih ketat sebenarnya). $S_5$

L = {σ_{1} \dots σ_{n} \in S_{5}^{*} ∣ σ_{1} \circ \dots \circ σ_{n} = Id}

$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$

L

$L$

{NC}^{1}

$\textrm{NC}^1$

{AC}^{0}

$\textrm{AC}^0$

Secara khusus ini menunjukkan bahwa bahasa-bahasa reguler tidak ada dalam jika . Dengan menggunakan teori semi-grup (lihat buku Straubing [1] untuk lebih jelasnya), kami memperoleh bahwa jika secara ketat di maka semua bahasa reguler adalah -complete atau . $\textrm{TC}^0$ $\textrm{TC}^0 \subsetneq \textrm{NC}^1$ $\textrm{ACC}^0$ $\textrm{NC}^1$ $\textrm{NC}^1$ $\textrm{ACC}^0$

[1] Straubing, Howard (1994). "Automata terbatas, logika formal, dan kompleksitas sirkuit". Kemajuan dalam Ilmu Komputer Teoritis. Basel: Birkhäuser. hal. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). "Program Percabangan Berukuran Polinomial Berikat Lebar Mengakui Tepatnya Bahasa-Bahasa Itu di NC1"

CP
sumber

Selain itu, jika ACC

adalah tidak "ketat NC

maka semua bahasa reguler" di ACC

pula.

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Bahasa reguler dengan monoids sintaksis terpecahkan adalah -Lengkap (karena Barrington, ini adalah alasan yang mendasari di balik hasil yang lebih sering dikutip bahwa sama dengan seragam lebar-5 program bercabang). Dengan demikian, bahasa tersebut tidak di kecuali . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Ekspresi reguler favorit saya yang lengkap adalah (ini sebenarnya merupakan penyandian , seperti pada jawaban CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Emil Jeřábek mendukung Monica
sumber

apa itu monoid sintaksis?

T ....

Peringatan terminologi yang membingungkan: dalam konteks ini, monoid dikatakan tidak dapat dipecahkan jika berisi grup yang tidak dapat diselesaikan sebagai sub - grup , tidak harus sebagai sub-tipe.

Emil Jeřábek mendukung Monica

Ekspresi reguler NC ^ 1-lengkap favorit saya adalah

(ini sebenarnya merupakan pengodean S_5, seperti dalam jawaban CP).

((a | b)^{3} (a b^{*} a | b))^{*}

$((a|b)^3(ab^*a|b))^*$

Emil Jeřábek mendukung Monica

Contoh lain, ringkas kurang tapi lebih mudah untuk memahami:

'a' bertindak sebagai siklus (1 2 3 4 5), " b "bertindak sebagai permutasi (1 2), dan kedua elemen grup tersebut diketahui menghasilkan

((a + b) (a b^{*} a b^{*} a b^{*} a + b))^{*}

$((a+b)(ab^*ab^*ab^*a+b))^*$

S - 5

$S-5$

@MichaelCadilhac:

bertindak sebagai

, dan

. Ini menghasilkan

karena

adalah transposisi.

a

$a$

(1, 2, 3, 4, 5)

$(1,2,3,4,5)$

b

$b$

(1, 2, 3, 4)

$(1,2,3,4)$

S_{5}

$S_5$

b a^{- 1}

$ba^{-1}$

Emil Jeřábek mendukung Monica