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

τ 1 τ 2 τ 3 τ j τ n

1

1

1

1

x 1 x 2 x i = 1 x n

Figure 9.9 When x i = 1thereisapath P to τ 1 such that each gate on P has value 1.

We now derive a stronger result: we show that every monotone circuit for binary merging
has a size that is Ω( n log n ) . Binary merging is realized by a function f ( n )

n n , n =

merge :

B →B

2 k , defined as follows: given two sorted binary k -tuples x and y , the value of f ( n )

merge ( x , y )
is the n -tuple that results from sorting the n -tuple formed by concatenating x and y .Thus,
a binary merging circuit can be obtained from one for sorting simply by restricting the values
assumed by inputs to the sorting circuit. (Binary merging is a subfunction of binary sorting.)
It follows that a lower bound on C Ω mon

f ( n )

merge is a lower bound on C Ω mon

f ( n )

sort .

THEOREM 9.6.2 Let n be even. Then the monotone circuit size for f ( n )

n n

merge :

B →B

satisfies

the following bounds:

C Ω mon f ( n )

merge = O ( n log n )

( n/ 2 )log 2 n − O ( n ) ≤

merge follows from the construction given in The-
orem 6.8.2 after max and min comparison operators are replaced by AND sand OR s, respec-
tively.
Let k = n/ 2. The function f ( n )

f ( n )

Proof The upper bound on C Ω mon

merge operates on two k -tuples x and y to produce the

merged result f ( n )

merge ( x , y ) ,where x and y are in descending order; that is, x 1

≥ x 2 ≥

···≥ x k and y 1 ≥ y 2 ≥···≥ y k . As stated above for binary sorting, the output functions

are τ 1 , τ 2 , ... , τ n .
Let x 1 = x 2 = ··· = x r− 1 = 1, x r + 1 = ··· = x k = 0, y 1 = y 2 = ··· = y s = 1,

and y s + 1 = = y k = 0. Let x r be unspecified. Since the circuit is monotone, the value

computed by each gate circuit is 0, 1, or x r .Also,

···

⎧
⎨

t<r + s

1

τ t ( x , y )= x r t = r + s

⎩

t>r + s

0

It follows that there must be a path P ( r + s r of gates from the input labeled x r to the
output labeled τ r + s such that each gate output is x r .If x r = 0, since the components of x