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

$\endgroup$
0

2 Answers 2

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"

$\endgroup$
1
  • 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, 2016 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).

$\endgroup$
9
  • 1
    $\begingroup$ what is a syntactic monoid? $\endgroup$
    – Turbo
    Jan 2, 2016 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$ Jan 2, 2016 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$ Jan 2, 2016 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, 2016 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$ Jan 3, 2016 at 10:40

Your Answer

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