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

prime implicant, there is such a gate G i , j .Furthermore, G i , j must be an AND gate because
OR gates cannot generate new prime implicants. Let G 1 and G 2 be gates generating inputs
for G i , j . Let them compute functions g 1 and g 2 . It follows from the definition of G i , j that
a i , k ∈ PI ( g 2 ) or vice versa. Let the former hold. If a i , k = 1, g 1 = 1

and G i , j can be eliminated. We now show that G i , j

PI ( g 1 ) and b k , j ∈

=( i , j ) . Suppose = G i , j

for ( i , j )

= j , there are at least three distinct variables among a i , k , a i , k , b k , j ,
and b k , j . Therefore either g 1 or g 2 has at least two of these variables as prime implicants.
By Lemma 9.6.2 this circuit is not minimal, a contradiction.

= i or j

not. Since i

We summarize the results of this section below.

THEOREM 9.6.5 The standard algorithm for f ( n , m , p )
MM

nm + mp np , the Boolean matrix

: B →B

multiplication function, is optimal. It uses nmp AND sand n ( m

−

1 ) p OR s.

We now show that the monotone circuit size of the clique function is exponential.

9.6.3 The Approximation Method
The approximation method is used to derive large lower bounds on the monotone circuit size
for certain monotone Boolean functions. In this section we use it to derive an exponential
lower bound on the size of the smallest monotone circuit for the clique function f ( n )

clique , k :

n ( n− 1 ) / 2

B . This method provides an interesting approach to deriving large lower bounds

on circuit size. However, as mentioned in the Chapter Notes, it is doubtful that it can be used
to obtain large lower bounds on circuit size over complete bases.
The approximation method converts a monotone circuit C computing a function f into
an approximation circuit C computing a function f . This is done by repeatedly replacing a
previously unvisited gate farthest away from the output gate by an approximation gate that
computes an approximation to the AND or OR gate it replaces. Each replacement operation
changes the circuit and increases by a small amount the number of input tuples on which f
and the function computed by the new circuit differ. When the entire replacement process is
complete, the resulting circuit approximates f poorly; that is, f and f differ on a large number
of inputs. For this to happen, the original monotone circuit must have had many gates, each
of which contributes a relatively small number of errors to the complete replacement process.
This is the essence of the approximation method.
There are a number of ways to approximate AND and OR gates in a monotone circuit.
Razborov [ 270 ], who introduced the approximation method, used an approximation for gates
based on clique indicators, monotone functions associated with a subset of a set of vertices
that has value 1 exactly when there is an edge between every pair of vertices in the subset. In
this section gates are approximated in terms of the SOPE and POSE forms, a method used by
Amano and Maruoka [ 20 ] to approximate the clique function.
It is not hard to show that the monotone circuit size of f ( n )
clique , k

→B

is O ( n n ) .(SeeProb-

clique , k have size C Ω mon f ( n ) clique , k

lem 9.37 .) We now show that all monotone circuits for f ( n ) ≥

2 ( 1 . 8 ) min( √ k− 1 / 2, n/ ( 2 k )) ,whichis2 Ω( n 1 / 3 ) for k proportional to n 2 / 3 .

1