期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth d with S gates can
be made to output a constant by setting O(S1−(d)) (where
(d)=4−d) of its input values. This implies a
superlinear size lower bound for a large class of functions. As a
consequence, we show that constant depth circuits of polynomial size
are strictly more powerful than constant depth circuits of linear
size. We give circuit constructions that show that the bound
O(S1−(d)) is near optimal.
