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

9.6.1 The Path-Elimination Method
In this section we illustrate the path-elimination method for deriving lower bounds on circuit
size for monotone functions. This method demonstrates that a path of gates in a monotone
circuit can be eliminated by fixing one input variable. Thus, it is the monotone equivalent
of the gate-elimination method for general circuits. We apply the method to two problems,
binary sorting and binary merging.
Consider computing the binary sorting function f ( n )
sort

n introduced in Sec-
tion 2.11 . This function rearranges the bits in a binary n -input string into descending order.
Thus, the first sorted output is 1 if one or more of the inputs is 1, the second is 1 if two or more
of them are 1, etc. Consequently, we can write f ( n )

n

: B →B

2 , ... , τ ( n n ) ,
where τ ( n t is the threshold function on n inputs with threshold t whose value is 1 if t or more
of its inputs are 1 and 0 otherwise. Ajtai, Komlos, and Szemeredi [ 14 ]haveshowntheexis-
tence of a comparator-based sorting network on n inputs of size O ( n log n ) .(Thecoefficient
on this bound is so large that the bound has only asymptotic value.) Such networks can be
converted to a monotone network by replacing the max and min operators in comparators
with OR and AND , respectively.

sort ( x 1 , x 2 , ... , x n )=( τ ( n )

, τ ( n )

1

THEOREM 9.6.1 The monotone circuit size for f ( n )

sort satisfies the following bounds:

f ( n )

sort = O ( n log n )

2 log 2 n ≤

n log 2 n − C Ω mon

Proof To derive the lower bound, we show that in any circuit for f ( n )
sort

there is an input

variable that can be set to 1, thereby allowing at least log 2 n gates along a path from it to

the output τ ( n )
1

to be removed from the circuit and converting the circuit to one for f ( n− 1 )
sort

.

As a result, we show the following relationship:

f ( n )

sort

f ( n− 1 )
sort

+

C Ω mon ≥ C Ω mon log 2 n

A simple proof by induction and a little algebra show that the desired result follows from
this bound and the fact that C Ω ( f ( 2 )

sort )= 2, which is easy to establish.

= i but let x i vary. The only functions computed at gates are 0, 1, or
x i . Also, the value of τ 1 ( x ) on such inputs is equal to x i . Consequently, there must be a
path P from the vertex labeled x i to τ 1 such that at each gate on the path the function x i is
computed. (See Fig. 9.9 .) Thus, if we set x i = 1when x j = 0for j

Let x j = 0for j

= i the output of each
of these gates is 1. Furthermore, since the circuit is monotone, each function computed at a
gate is monotone (see Problem 2 ). Thus, if any other input is subsequently increased from
0 to 1, the value of τ 1 and of all the gates on the path P from x i remain at 1 and can be
removed. This setting of x i also has the effect of reducing the threshold of all other output
functions by 1 and implies that the circuit now computes the binary sorting function on one
fewer variable.
Consider a minimal monotone circuit for f ( n )

sort . The shortest paths from each input to
the output τ ( n 1 form a tree of fan-in 2. From Theorem 9.3.1 there is a path in this tree from
some input, say x r ,to τ ( n )

log 2 n that has length at least . Consequently the shortest path

1

from x r to τ ( n )

has length at least log 2 n , implying that at least log 2 n gates can be

1

removed if x r is set to 1.