Regular versus TC0

De acordo com o Complexity Zoo , e sabemos que não pode contar, portanto . No entanto, ele não diz se ou não. Como não conhecemos , também não sabemos . $\mathsf{Reg} \subseteq \mathsf{NC^1}$ $\mathsf{Reg}$ $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$ $\mathsf{Reg} \subseteq \mathsf{TC^0}$ $\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$ $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$

Existe um candidato para um problema no $\mathsf{Reg}$ que não esteja no $\mathsf{TC^0}$ ?

Existe um resultado condicional implicando que $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$ , por exemplo, se $\mathsf{NC^1} \not\subseteq \mathsf{TC^0}$ depois $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$ ?

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

Respostas:

Tome como alfabeto e Barrington provou em [2] que é -complete a redução (e mesmo com uma redução mais restritiva, na verdade). $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$

Em particular, isso mostra que os idiomas regulares não estão em $\textrm{TC}^0$ se $\textrm{TC}^0 \subsetneq \textrm{NC}^1$ . Usando a teoria dos semigrupos (veja o livro de Straubing [1] para obter mais detalhes), obtemos que se $\textrm{ACC}^0$ estiver estritamente em $\textrm{NC}^1$ , todos os idiomas regulares serão $\textrm{NC}^1$ -complete ou $\textrm{ACC}^0$ .

[1] Straubing, Howard (1994). "Autômatos finitos, lógica formal e complexidade de circuitos". Progresso em Ciência da Computação Teórica. Basileia: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). "Programas de ramificação de tamanho polinomial de largura limitada reconhecem exatamente esses idiomas no NC1"

CP
fonte

Além disso, se ACC não estiver "estritamente em NC , todos os idiomas regulares estarão" em ACC qualquer maneira.

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Linguagens regulares com monoides sintáticos insolúveis são (completas) (devido a Barrington; esta é a razão subjacente ao resultado mais comumente citado de que é igual a programas de ramificação uniformes com largura 5). Assim, qualquer idioma desse tipo não está em menos que . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Minha expressão regular completa favorita de é (na verdade, é uma codificação de , como na resposta da CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Emil Jeřábek apoia Monica
fonte

o que é um monóide sintático?

T ....

Aviso de terminologia confusa: neste contexto, diz-se que um monóide é insolúvel se contiver um grupo insolúvel como sub- grupo , não necessariamente como submonóide.

Emil Jeřábek apoia Monica

Minha expressão regular completa completa de NC ^ 1 é

(na verdade, é uma codificação de S_5, como na resposta de CP).

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

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

Emil Jeřábek apoia Monica

Outro exemplo, menos conciso, mas mais fácil de entender:

o 'a' atua como o ciclo (1 2 3 4 5), o " b "atuam como a permutação (1 2), e sabe-se que esses dois elementos do grupo geram

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

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

S - 5

$S-5$

@MichaelCadilhac:

actua como

, e

como

. Eles geram

pois

é uma transposição.

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 apoia Monica