15
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
17
$\begingroup$

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"

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Furthermore, if ACC$^0$ is not "strictly in NC$^1$ then all regular languages are" in ACC$^0$ anyway. $\;\;\;\;$ $\endgroup$ – user6973 Jan 3 '16 at 1:58
15
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ what is a syntactic monoid? $\endgroup$ – T.... Jan 2 '16 at 18:28
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 2 '16 at 18:40
  • 2
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Jan 2 '16 at 18:55
  • 5
    $\begingroup$ 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$. $\endgroup$ – C.P. Jan 3 '16 at 8:35
  • 3
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Jan 3 '16 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.