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

CHAPTER

Circuit Complexity

The circuit complexity of a binary function is measured by the size or depth of the smallest
or shallowest circuit for it. Circuit complexity derives its importance from the corollary to
Theorem 3.9.2 ; namely, if a function has a large circuit size over a complete basis of fixed
fan-in, then the time on a Turing machine required to compute it is large. The importance of
this observation is illustrated by the following fact. For n

1, let f ( n )
L

≥

be the characteristic

function of an NP -complete language L ,where f ( n )
L

has value 1 on strings of length n in L

and value 0 otherwise. If f ( n )
L

has super-polynomial circuit size for all sufficiently large n ,then

P = NP .

In this chapter we introduce methods for deriving lower bounds on circuit size and depth.
Unfortunately, it is generally much more difficult to derive good lower bounds on circuit
complexity than good upper bounds; an upper bound measures the size or depth of a particular
circuit whereas a lower bound must rule out a smaller size or depth for all circuits. As a
consequence, the lower bounds derived for functions realized by circuits over complete bases
of bounded fan-in are often weak.
In attempting to understand lower bounds for complete bases, researchers have studied
monotone circuits over the monotone basis and bounded-depth circuits over the basis

{

AND ,

}

in which the first two gates are allowed to have unbounded fan-in. Formula size,
which is approximately the size of the smallest circuit with fan-out 1, has also been studied.
Lower bounds to formula size also produce lower bounds to circuit depth, a measure of the
parallel time needed for a function.
Research on these restricted circuit models has led to some impressive results. Exponential
lower bounds on circuit size have been derived for monotone functions over the monotone
basis and functions such as parity when realized by bounded-depth circuits. Unfortunately,
the methods used to obtain these results may not apply to complete bases of bounded fan-in.
Fortunately, it has been shown that the slice functions have about the same circuit size over
both the monotone and standard (non-monotone) bases. This may help resolve the P = NP
question, since there are NP -complete slice problems.
Despite the difficulty of deriving lower bounds, circuit complexity continues to offer one
of the methods of highest potential for distinguishing between P and NP .

OR , NOT

391