A generalization of Spira's theorem and circuits with small segregators or separators

摘要

Spira showed that any Boolean formula of size s can be simulated in depth O(logs). We generalize Spira's theorem and show that any Boolean circuit of size s with segregators (or separators) of size f(s) can be simulated in depth O(f(s) logs). This improves and generalizes a simulation of polynomial-size Boolean circuits of constant treewidth k in depth O(k~2 log n) by Jansen and Sarma. Our results imply that the class of languages computed by non-uniform families of polynomial-size circuits with constant size segregators equals non-uniform NC. As a corollary, we show that the Boolean Grcuit Value problem for circuits with constant size segregators is in deterministic SPACE(log~2 n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE(n~(1/2)log n); and that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPKE(n~(1/2)).