Circuit Complexity - Models of Computation: Exploring the Power of Computing - page 400

THEOREM 9.3.1 Let f : B

n

→B

be dependent on each of its n variables. Then over each basis

Ω of

fan-in r ,thesizeanddepthof f satisfies the following lower bounds:

n

− 1

C Ω ( f ) ≥

r −

1

D Ω ( f ) ≥ log r n

Proof Consider a circuit of size C Ω ( f ) for f . Since it has fan-in r , it has at most rC Ω ( f )
edges between gates. After we show that this circuit also has at least C Ω ( f )+ n

−

1edges,

we observe that rC Ω ( f )

≥ C Ω ( f )+ n −

1, from which the conclusion follows.
Since f depends on each of its n variables, there must be at least one edge attached to
each of them. Similarly, because the circuit has minimal size there must be at least one edge
attached to each of the C Ω ( f ) gates except possibly for the output gate. Thus, the circuit
has at least C Ω ( f )+ n

−

1 edges and the conclusion follows.
The depth lower bound uses the fact that a circuit with depth d and fan-in r with the
largest number of inputs is a tree. Such trees have at most r d leaves (input vertices). Because
f depends on each of its variables, a circuit for f of depth d has at least n and at most r d
leaves, from which the depth lower bound follows.

This lower bound is the best possible given the information used to derive it. To see this,
observe that the function f ( x 1 , x 2 , ... , x n )= x 1

∧ x 2 ∧···∧ x n , which depends on each of

its variables, has circuit size ( n − 1 ) / ( r − 1 ) and depth log r n over the basis containing

the r -input AND gate. (See Problem 9.15 .)

9.3.2 The Gate-Elimination Method for Circuit Size
The search for methods to derive large lower bounds on circuit size for functions over complete
bases has to date been largely unsuccessful. The largest lower bounds on circuit size that have
been derived for explicitly defined functions are linear in n , the number of variables on which
the functions depend. Since most Boolean functions on n variables have exponential size (see
Theorem 2.12.1 ), functions do exist that have high complexity. Unfortunately, this fact doesn't
help us to show that any particular problem has high circuit size. In particular, it does not help
us to show that P

= NP .
In this section we introduce the gate-elimination method for deriving linear lower bounds.
When applied with care, it provides the strongest known lower bounds for complete bases.
The gate-elimination method uses induction on the properties of a function f on n variables
to show two things: a) a few variables of f can be assigned values so that the resulting function
is of the same type as f , and b) a few gates in any circuit for f can be eliminated by this
assignment of values. After eliminating all variables by assigning values to them, the function
is constant. Since the number of gates in the original circuit cannot be smaller than the number
removed during this process, the original circuit has at least as many gates as were removed.
We now apply the gate-elimination method to functions in the class Q ( n )

2,3 defined below.
Functions in this class have at least three different subfunctions when any pair of variables
ranges through all four possible assignments.

DEFINITION 9.3.1 A Boolean function f : B belongs to the class Q ( n )

n

2,3 if for any two
variables x i and x j , f has at least three distinct subfunctions as x i and x j range over all possible

→B