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.