## Every NL set has constant-depth Boolean circuits of sub-exponential
size

(folklore?)

#### Preface

Here is another post regarding
(a somewhat old result re) the power of constant-depth
Boolean circuits of sub-exponential size.
It seems folklore,
but please correct me in case I am wrong about that
(or about anything else...).
In any case, the result is obtained by natural generalization
of the well-known idea underlying Savitch's Theorem.

#### The actual post

**THM:** *Every set in NL has constant-depth Boolean circuits
of sub-exponential size.*
That is, for every such set $S$, there exists a constant $c$ such that
for any constant $d>c$, the set $S$ has depth-$d$ circuits of
size $exp(n^{c/d})$ (unbounded fan-in, of course).

This can be proved by generalizing the idea that underlies
the proof of Savitch Theorem.
The closest description I am aware of is in Section 3.2
of Dieter van Melkebeek survey [vM],
where it is presented in terms of alternating time.

In any case, let's do it in terms of NL,
or rather show that directed st-connectivity can be solved
by depth-$d$ circuits of size $exp(\tildeO(n^{2/d}))$,
where $n$ denotes the number of vertices
(and $d$ factors are omitted in the tildeO-notation).
Let $Phi(G,u,v,\ell)$ denote the predicate indicating that there is a path
of length at most $\ell$ from $u$ to $v$ in the graph $G$.
Then, observe that $Phi(G,v_0,v_{m+1},\ell)$ can be written as

$$\exists v_1,...,v_m \forall i\in[m+1] Phi(G,v_{i-1},v_{i},\ceil(\ell/m))$$

Now, picking $m=n^{2/d}$ and recursing for $d/2$ steps,
we obtain the desired circuit (by replacing the existential quantifiers
with $2^{m\log_2n}$-way OR-gates and the universals with AND-gates).
[vM] Dieter van Melkebeek.
A Survey of Lower Bounds for Satisfiability and Related Problems.
Foundations and Trends in Theoretical Computer Science,
Vol. 2, pages 197-303, 2007.

Back to
list of Oded's choices.