کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427839 | 686565 | 2011 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The size and depth of layered Boolean circuits The size and depth of layered Boolean circuits](/preview/png/427839.png)
We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth O(slogs). For synchronous circuits of size s , we obtain simulations of depth O(s). The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that D(f)=O(C(f)/logC(f)), where C(f)C(f) and D(f)D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.
Research highlights
► We consider the size versus depth problem for special Boolean circuits.
► Results for layered circuits and synchronous circuits are presented.
► Layered circuits of size s can be simulated in depth O(slogs).
► Synchronous circuits of size s can be simulated in depth O(s).
Journal: Information Processing Letters - Volume 111, Issue 5, 1 February 2011, Pages 213–217