CIRCUIT BOTTOM FAN-IN AND COMPUTATIONAL POWER

We investigate the relationship between circuit bottom fan-in and circ uit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove t hat there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for cir cuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size . Based on this scheme, we are able to prove, for example, that for an y integer c, there are functions that are computable by circuits of li near size and depth k with bottom fan-in O(log n) but that require exp onential size for circuits of depth k with bottom fan-in c, and that f or any constant epsilon > 0, there are functions that are computable b y circuits of linear size and depth k with bottom fan-in log n but tha t require superpolynomial size for circuits of depth k with bottom fan -in O(log(1-epsilon) n). A consequence of these results is that the th ree input read-modes of alternating Turing machines proposed in the li terature are all distinct.