Zwykły kontra TC0

Według Zoo Złożoności , $\mathsf{Reg} \subseteq \mathsf{NC^1}$ i wiemy, że $\mathsf{Reg}$ nie może się liczyć, więc $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$ . Jednakże nie mówi, czy $\mathsf{Reg} \subseteq \mathsf{TC^0}$ czy nie. Ponieważ nie znamy $\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$ , nie znamy również $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$ .

Czy jest kandydatem do problemu w , który nie jest w ? $\mathsf{Reg}$ $\mathsf{TC^0}$

Czy istnieje wynik warunkowy sugerujący, że , np. Jeśli to ? $\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
źródło

Odpowiedzi:

Weź jako alfabet i Barrington udowodnił w [2], że jest -kompletne dla redukcji (a nawet z bardziej restrykcyjna redukcja). $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$

W szczególności pokazuje to, że zwykłe języki nie są w jeśli . Stosując teorię półgrup (więcej szczegółów znajduje się w książce Straubinga [1]), otrzymujemy, że jeśli jest ściśle w wówczas wszystkie zwykłe języki są albo kompletne albo . $\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). „Automaty skończone, logika formalna i złożoność obwodów”. Postęp w informatyce teoretycznej. Bazylea: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). „Wielomianowe programy rozgałęziające o ograniczonej szerokości rozpoznają dokładnie te języki w NC1”

CP
źródło

Ponadto, jeśli ACC

nie jest „ściśle w NC

wówczas wszystkie zwykłe języki są” w ACC

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Zwykły języki z nierozwiązywalne składniowych monoids są -Complete (ze względu na Barrington, co jest powodem za bardziej powszechnie cytowane wyniku czego równa jednakowe szerokości 5 programów rozgałęzienia). Tak więc, każdy taki język nie jest ile nie . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Moim ulubionym wyrażeniem regularnym zawierającym jest (w rzeczywistości jest to kodowanie , jak w odpowiedzi CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Emil Jeřábek 3.0
źródło

co to jest monoid składniowy?

T ....

Ostrzeżenie przed mylącą terminologią: w tym kontekście mówi się, że monoid jest nierozwiązywalny, jeśli zawiera nierozwiązywalną grupę jako podgrupę , niekoniecznie jako submonoid.

Emil Jeřábek 3.0

Moje ulubione wyrażenie regularne z NC ^ 1 to

(w rzeczywistości jest to kodowanie S_5, jak w odpowiedzi CP).

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

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

Emil Jeřábek 3.0

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

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

S - 5

$S-5$

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}$