16

According to the Complexity Zoo, $\mathsf{Reg} \subseteq \mathsf{NC^1}$ and we know that $\mathsf{Reg}$ cannot count so $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$. However it doesn't say if $\mathsf{Reg} \subseteq \mathsf{TC^0}$ or not. Since we don't know $\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$ we also don't know $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$.

Is there a candidate for a problem in $\mathsf{Reg}$ that is not in $\mathsf{TC^0}$?

Is there a conditional result implying that $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$, e.g. if $\mathsf{NC^1} \not\subseteq \mathsf{TC^0}$ then $\mathsf{Reg} \not\subseteq \mathsf{TC^0}$?

Community
  • 1
Kaveh
  • 21,577
  • 8
  • 82
  • 183

2 Answers2

17

Take $S_5$ as alphabet and $$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$ Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}^0$ reduction (and even with a more restrictive reduction actually).

In particular this shows that regular languages are not in $\textrm{TC}^0$ if $\textrm{TC}^0 \subsetneq \textrm{NC}^1$. By using semigroups theory (see the book of Straubing [1] for more details), we obtain that if $\textrm{ACC}^0$ is strictly in $\textrm{NC}^1$ then all regular languages are either $\textrm{NC}^1$-complete or $\textrm{ACC}^0$.

[1] Straubing, Howard (1994). "Finite automata, formal logic, and circuit complexity". Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1"

C.P.
  • 992
  • 5
  • 12
  • 1
    Furthermore, if ACC$^0$ is not "strictly in NC$^1$ then all regular languages are" in ACC$^0$ anyway. $;;;;$ –  Jan 03 '16 at 01:58
15

Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals uniform width-5 branching programs). Thus, any such language is not in $\mathrm{TC}^0$ unless $\mathrm{TC}^0=\mathrm{NC}^1$.

My favorite $\mathrm{NC}^1$-complete regular expression is $((a|b)^3(ab^∗a|b))^∗$ (this is actually an encoding of $S_5$, as in C.P.'s answer).

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
  • 2
    what is a syntactic monoid? – Turbo Jan 02 '16 at 18:28
  • 1
    https://en.wikipedia.org/wiki/Syntactic_monoid – Emil Jeřábek Jan 02 '16 at 18:34
  • 3
    Warning of confusing terminology: in this context, a monoid is said to be unsolvable if it contains an unsolvable group as a subsemigroup, not necessarily as a submonoid. – Emil Jeřábek Jan 02 '16 at 18:40
  • 2
    My favourite NC^1-complete regular expression is $((a|b)^3(ab^a|b))^$ (this is actually an encoding of S_5, as in C.P.'s answer). – Emil Jeřábek Jan 02 '16 at 18:55
  • So basically asking if there is a DFA not implementable in TC0 or in other words is graph reachability in TC0 right? – Turbo Jan 02 '16 at 19:00
  • Would you mind indicating how $((a|b)^3(ab^a|b))^$ encodes $S_5$? Thanks! – Michaël Cadilhac Jan 03 '16 at 05:29
  • 5
    Another example, less concise but easier to understand: $$((a+b)(ab^ab^ab^a+b))^$$ the 'a' act as the cycle (1 2 3 4 5), the "b" act as the permutation (1 2), and those two group element are known to generate $S-5$. – C.P. Jan 03 '16 at 08:35
  • 3
    @MichaelCadilhac: $a$ acts as $(1,2,3,4,5)$, and $b$ as $(1,2,3,4)$. These generate $S_5$ as $ba^{-1}$ is a transposition. – Emil Jeřábek Jan 03 '16 at 10:40
  • @EmilJeřábek 1) If $REG$ is complete for $NC^1$ then because $TC^0$ is in $NC^1$ it seems $REG$ can count. Is it correct? 2) If $TC^0\neq NC^1$ is $ACC^0\neq TC^0$ unconditionally or is it possible $ACC^0=TC^0\neq NC^1$ is still allowed? – Turbo Jun 06 '21 at 12:25