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

To show the existence of the vertex-disjoint paths, let y 1 = y 2 =

···

= y s = 1,

y s + 1 = = x r− 1 = 1, but let x r , x r + 1 , ... , x k be

unspecified. Then τ r + s = x r and, as stated above, there is a path P ( r + s r of gates from an
input labeled x r to the output labeled τ r + s such that each gate has value x r .Set x r = 1.
Reasoning as before, there must be a path P ( r + 1 + s )

··· = y k = 0and x 1 = x 2 = ···

r + 1 of gates from an input labeled x r + 1 to
the output labeled τ r + 1 + s such that each gate has value x r + 1 .Thus, P ( r + 1 + s )

and P ( r + s ) r

are vertex-disjoint. Extending this idea, we have the desired conclusion about disjoint paths.
We now develop a second fact about these paths that is needed in the lower bound. Let
P ( r + s r be a path from x r to τ r + s , as suggested in Fig. 9.11 (a). Those paths connecting
inputs to any one output form a binary tree, as suggested in Fig. 9.11 (b). The number of
inputs from which there is a path to τ j is e ( j ) , the number of inputs on which τ j depends.
To derive the lower bound on C Ω mon ( f ( n )

r + 1

merge ) ,let d ( i , j ) denote the length (number
of edges or non-input vertices (gates)) on the shortest path from an input labeled x i to the
output labeled τ j .(Clea l , d ( i , j )= 0unless i

i + k .) Since the path from
input x i to output τ j described above has a length at least as large as d ( i , j ) , it follows that
C Ω mon

≤ j ≤

f ( n )

merge satisfies the following bound:

max k k

C Ω mon f ( n )

merge

≥ d ( r , r + s ) | 0 ≤ s ≤

r = 1

Since the maximum of a set of integers is at least equal to the average of these integers, we
have the following for k = n/ 2 ≥ 1:

C Ω mon f ( n )

merge

k k 2 k k

1
k + 1

1
k + 1

≥ d ( r , r + s )= d ( i , j )

s = 0 r = 1 j = 1 i = 1

The last identity follows by using the fact that d ( i , j )= 0unless i i + k .But

i = 1 d ( i , j ) is the sum of the distances of the shortest paths from the relevant inputs of x to
output τ j ,1

≤ j ≤

2 k . Since these paths form a binary tree and τ j depends on e ( j ) inputs,
this is the external path length of a tree with e ( j ) leaves. The external path length is at least
e ( j )

≤ j ≤

2 log 2 e ( j ) + e ( j ) (see Problem 9.4 ). In turn, x 2 log 2 x + x

log 2 e ( j ) − log 2 x − ≥

2 log 2 x + x =

x log 2 x ,because log 2 x =(log 2 x )+ δ for 0 ≤ δ< 1and x log 2 x −

2 δ + δ is easily shown to be a concave function whose
minimum value occurs at either δ = 0or δ = 1, both of which are 0. Thus, 1

2 δ + δ ) ,where1

x log 2 x + x ( 1 − −

2 δ + δ 0

and the result follows. Thus, the size of smallest monotone circuit satisfies the following
lower bound when n = 2 k :

− ≥

f ( n )

merge

2 k

1
k + 1

C Ω mon ≥ [ e ( j )log 2 e ( j )]

j = 1

k

2
k + 1

= [ j log 2 j ]

j = 1

The last equality uses the definition of e ( j ) given above. By applying the reasoning in
Problem 2.1 and captured in Fig. 2.23 , it is easy to show that the above sum is at least as