Loading...
Please wait, while we are loading the content...
Similar Documents
A generalization of spira’s theorem and circuits with small segregators or separators.
| Content Provider | CiteSeerX |
|---|---|
| Author | Gál, Anna Jang, Jing-Tang |
| Abstract | Abstract. Spira [28] showed that any Boolean formula of size s can be simulated in depth O(log s). We generalize Spira’s theorem and show that any Boolean circuit of size s with segregators of size f(s) can be simulated in depth O(f(s) log s). If the segregator size is at least s ε for some constant ε> 0, then we can obtain a simulation of depth O(f(s)). 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 [17]. Since the existence of small balanced separators in a directed acyclic graph implies that the graph also has small segregators, our results also apply to circuits with small separators. Our results imply that the class of languages computed by non-uniform families of polynomial-size circuits that have constant size segregators equals non-uniform NC 1. Considering space bounded Turing machines to generate the circuits, for f(s) log 2 s-space uniform families of Boolean circuits our small-depth simulations are also f(s) log 2 s-space uniform. As a corollary, we show that the Boolean Circuit Value problem for circuits with constant size segregators (or separators) is in deterministic SP ACE(log 2 n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete [16], can be solved in deterministic SP ACE ( √ n log n). Key words: Boolean circuits, circuit size, circuit depth, Spira’s theorem, Turing machines, space complexity 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Spira Theorem Small Segregator Boolean Circuit Deterministic Sp Ace Constant Size Segregator Boolean Formula Non-uniform Nc Constant Treewidth S-space Uniform Family Turing Machine Small-depth Simulation Circuit Depth Segregator Size Planar Circuit Value Problem Polynomial-size Circuit Boolean Circuit Value Problem Small Separator S-space Uniform Circuit Size Non-uniform Family Directed Acyclic Graph Implies Polynomial-size Boolean Circuit Small Balanced Separator Space Complexity |
| Content Type | Text |
| Resource Type | Article |
