2
$\begingroup$

Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.

Is this class closed under Kleene star? I thought it would be simple since it is easy to check every subword (using a polynomial number of gates), but the part where I have to check every partition makes the circuit linear in depth.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Denote your language by $L$. Let the input be $x_1,\ldots,x_n$. Let $f(i,j,\ell)$ be true if $x_1,\ldots,x_j \in L^\ell$. The output will be $$ \bigvee_{\ell=1}^n f(1,n,\ell). $$ When $\ell = 1$, there is an $\mathsf{AC^1}$ circuits for $f(i,j,\ell)$. When $\ell > 1$, we use the formula $$ f(i,j,\ell) = \bigvee_{k=i}^{j-1} (f(i,k,\lfloor \ell/2 \rfloor) \land f(k+1,j,\lceil\ell/2\rceil)). $$ The resulting circuit is still $\mathsf{AC^1}$, since there are only $O(\log n)$ levels of recursion.

A different way of looking at this construction is to notice that for inputs of length $L$, we can replace $L^*$ with $L \cup \cdots \cup L^n$; and that $L^m$ can be computed in $O(\log m)$ steps using repeated squaring.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I posit this circuit is not in $AC^1$, since it is not of polynomial size. Let $s(i, j, l)$ be the size of the circuit for $f(i, j, l)$. We can generously assume $s(i, j, 1) \geq 1$. Thus $s(1, n, l) = \sum_{k = 1}^{n - 1} s(1, k, l / 2) + s(k + 1, n, l / 2)$ for which the best limit I can think of is $\mathcal{O}(n s(1, n, l / 2))$. And the recurrence relation $g(n) = ng(n/2), g(1) = 1$ solves to $\mathcal{O}(n^{\log n})$, which is quasipolynomial. I might be wrong, but either way, I'd say that you need to prove that the result has polynomial size, as it is not immediately obvious. $\endgroup$
    – V0ldek
    Dec 20, 2020 at 16:03
  • $\begingroup$ By the way, I'm not smart enough to solve that recurrence equation by myself, but fortuantely Wolfram Alpha is. $\endgroup$
    – V0ldek
    Dec 20, 2020 at 16:06
  • $\begingroup$ You can compute each $f(i,j,\ell)$ from other values of $f$ using $O(n)$ gates. Since there are $O(n^3)$ many choices for $i,j,\ell$, the resulting circuit has $O(n^4)$ gates. $\endgroup$
    – Yuval Filmus
    Dec 20, 2020 at 16:12
  • 1
    $\begingroup$ Your recurrence might make sense if we were constructing a formula. Fortunately, we are constructing a circuit, so we only have to compute each $f(i,j,\ell)$ once. This is akin to dynamic programming. $\endgroup$
    – Yuval Filmus
    Dec 20, 2020 at 16:13
  • $\begingroup$ Right, so my naive way would take some subproblem circuits more than once, but if we deduplicate that we get a straightforward limit of $\mathcal{O}(n^3)$. That does make sense, thanks. $\endgroup$
    – V0ldek
    Dec 20, 2020 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.