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

作者：Gal Anna^*; Jang Jing Tang

来源：Information and Computation, 2016, 251: 252-262.

DOI：10.1016/j.ic.2016.09.008

• Boolean circuits
• Circuit size
• Circuit depth
• Spira's theorem
• Space complexity

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) logn) by Jansen and Sarnia. Our results imply that the class of languages computed by non-uniform families of polynomial-size circuits with constant size segregators equals non-uniform NC1.
As a corollary, we show that the Boolean Circuit 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(root nlogn); and that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(root n).

• 出版日期2016-12