1.4 Non-Uniform Models (Circuits and Advice) 35
(two-argument) Boolean operations that we allow is immaterial (as long as
we consider a “full basis” of such operations, i.e., a set of operations that can
implement any other two-argument Boolean operation). Such circuits are called
circuits of
bounded fan-in. In contrast, other studies are concerned with circuits
of
unbounded fan-in, where each gate may have an arbitrary number of incoming
edges. Needless to say, in the case of circuits of unbounded fan-in, the choice
of allowed Boolean operations is important and one focuses on operations that
are “uniform” (across the number of operands, e.g., ∧ and ∨). Unless specified
differently, we shall refer to circuits of unbounded fan-in; however, in many of
the cases that we consider, the choice is immaterial.
1.4.1.2 Circuit Complexity
As stated earlier, the Boolean circuit model is used in Complexity Theory
mainly as a basis for defining a (non-uniform) complexity measure. Specifically,
the complexity of circuits is defined as their size.
Circuit Size as a Complexity Measure. The
size of a circuit is the number
of its edges. When considering a family of circuits (C
n
)
n∈N
that computes a
function f : {0, 1}
∗
→{0, 1}
∗
, we are interested in the size of C
n
as a function
of n. Specifically, we say that this family has size complexity s : N → N if for
every n the size of C
n
is s(n). The circuit complexity of a function f , denoted
s
f
, is the infimum of the size complexity of all families of circuits that compute
f . Alternatively, for each n we may consider the size of the smallest circuit
that computes the restriction of f to n-bit strings (denoted f
n
), and set s
f
(n)
accordingly. We stress that non-uniformity is implicit in this definition, because
no conditions are made regarding the relation between the various circuits used
to compute the function on different input lengths.
19
On the Circuit Complexity of Functions. We highlight some simple facts
regarding the circuit complexity of functions. These facts are in clear corre-
spondence to facts regarding Kolmogorov Complexity mentioned in §1.3.4.2,
and establishing them is left as an exercise (see Exercise 1.15).
1. Most importantly, any Boolean function can be computed by some fam-
ily of circuits, and thus the circuit complexity of any function is well
basis allows for emulating any two-argument operation by a constant size circuit. Indeed, in
both cases, we disregard constant factor changes in the circuit size.
19
Advanced comment: We also note that, in contrast to footnote 11, the circuit model and the
corresponding (circuit size) complexity measure support the notion of an optimal computing
device: Each function f has a unique size complexity s
f
(and not merely upper and lower
bounds on its complexity).