Обычный против TC0

Согласно Сложности Zoo , и мы знаем, что не может сосчитать, поэтому . Однако это не говорит, если или нет. Поскольку мы не знаем мы также не знаем . $\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}$

Есть ли кандидат в проблему в , которой нет в ? $\mathsf{Reg}$ $\mathsf{TC^0}$

Есть ли условный результат, подразумевающий, что , например, если то ? $\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 Кава
источник

Ответы:

Возьмем в качестве алфавита и Баррингтон доказано в [2] , что является -полным для редукции (и даже с более ограничительное сокращение на самом деле). $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$

В частности, это показывает, что обычные языки отсутствуют в если . Используя теорию полугрупп (подробнее см. Книгу Штраубинга [1]), мы получаем, что если строго в то все регулярные языки либо -полны, либо . $\textrm{TC}^0$ $\textrm{TC}^0 \subsetneq \textrm{NC}^1$ $\textrm{ACC}^0$ $\textrm{NC}^1$ $\textrm{NC}^1$ $\textrm{ACC}^0$

[1] Штраубинг, Говард (1994). «Конечные автоматы, формальная логика и сложность схем». Прогресс в теоретической информатике. Базель: Биркхойзер. п. 8. ISBN 3-7643-3719-2.

[2] Баррингтон, Дэвид А. Микс (1989). «Программы ветвления полиномиального размера ограниченной ширины распознают именно эти языки в NC1»

CP
источник

Кроме того, если ACC

является не «строго в NC

, то все регулярные языки» в АСС

в любом случае.

^{0}

$^0$

^{1}

$^1$

^{0}

$^0$

$\;\;\;\;$

Обычные языки с неразрешимыми синтаксическими моноидами являются -полными (из-за Баррингтона; это является основной причиной более часто цитируемого результата, что равняется программам ветвления с одинаковой шириной 5). Таким образом, любого такого языка нет в если только . $\mathrm{NC}^1$ $\mathrm{NC}^1$ $\mathrm{TC}^0$ $\mathrm{TC}^0=\mathrm{NC}^1$

Мой любимый -полное регулярное выражение: (на самом деле это кодировка , как в ответе CP). $\mathrm{NC}^1$ $((a|b)^3(ab^∗a|b))^∗$ $S_5$

Эмиль Йержабек поддерживает Монику
источник

что такое синтаксический моноид?

T ....

Предупреждение о запутанной терминологии: в этом контексте моноид называется неразрешимым, если он содержит неразрешимую группу как подполугруппу , а не как субмоноид.

Эмиль Йержабек поддерживает Монику

Мое любимое NC ^ 1-полное регулярное выражение:

(на самом деле это кодировка S_5, как в ответе CP).

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

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

Эмиль Йержабек поддерживает Монику

Другой пример, менее краткий, но более легкий для понимания:

«a» действует как цикл (1 2 3 4 5), b "действует как перестановка (1 2), и эти два элемента группы, как известно, генерируют

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

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

S - 5

$S-5$

@MichaelCadilhac:

действует как

, а

как

. Они генерируют

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

Эмиль Йержабек поддерживает Монику