Complexity Classes - Models of Computation: Exploring the Power of Computing - page 373

we can develop large lower bounds on the size or depth of circuits without regard to whether or
not they are drawn from a uniform family, then such lower bounds apply to uniform families
as well and, in particular, to other models of computation, such as Turing machines. For this
reason non-uniform circuits are important.
A circuit is a form of unstructured parallel machine, since its gates can operate in parallel.
The parallel random-access machine (PRAM) introduced in Chapter 1 and examined in Chap-
ter 7 is another important parallel model of computation in terms of which the performance
of many other parallel computational models can be measured. In Section 8.14 we show that
circuit size and depth are related to number of processors and time on the PRAM. These results
emphasize the important role of circuits not only in the construction of machines, but also in
measuring the serial and parallel complexity of computational problems.
Throughout the following sections we assume that circuits are constructed from gates cho-
sen from the standard basis Ω 0 =

{ }

.
We now explore uniform and non-uniform circuit families, thereby setting the stage for
the next chapter, in which methods for deriving lower bounds on the size of circuits are devel-
oped. After introducing uniform circuits we show that uniform families of circuits and Turing
machines compute the same functions. We then introduce a number of languages defined in
terms of the properties of families of circuits that recognize them.

AND , OR , NOT

8.13.1 Uniform Families of Circuits
Families of circuits are useful in characterizing decision problems in which the set of instances
is unbounded. One circuit in each family is associated with the “Yes” instances of each length:
it has value 1 on the “Yes” instances and value 0 otherwise.
Families of circuits are designed in Chapter 3 to simulate computations by finite-state,
random-access, and Turing machines on arbitrary numbers of inputs. For each machine M
of one of these types, there is a DTM S ( M ) such that on an input of length n , S ( M ) can
produce as output the description of a circuit on n inputs that computes exactly the same
function as does M on n inputs. (See the program in Fig. 3.27 .) These circuits are generated
in a uniform fashion.
On the other hand, non-uniform circuit families can be used to define non-computable
languages. For example, consider the family in which the n th circuit, C n ,isdesignedtohave
value 1 on those strings w of length n in the language

L 1 defined in Section 5.7 and value 0
otherwise. Such a circuit realizes the minterm defined by w . As shown in Theorem 5.7.4 ,

L 1

is not recursively enumerable; that is, there is no Turing machine that can recognize it.
This example motivates the need to identify families of circuits that compute functions
computable by Turing machines, that is, uniform families of circuits.

DEFINITION 8.13.1 A circuit family C = {C 1 , C 2 , C 3 , ...} is a collection of logic circuits in
which C n has n inputs and m ( n ) outputs for some function m : ￿

→

.
Atime- r ( n ) (space- r ( n ) ) uniform circuit family is a circuit family for which there is a
deterministic Turing machine M such that for each integer n supplied in unary notation, namely
1 n ,onitsinputtape, M writes the description of C n on its output tape using time (space) r ( n ) .
A log-space uniform circuit family is one for which the temporary storage space used by a
Turing machine that generates it is O (log n ) ,where n is the length of the input. The function
f : B ∗ →B ∗

is computed by C if for each n ≥ 1 , f restricted to n inputs is the function

computed by C n .