46 1 Computational Tasks and Models
Exercise 1.15 (on the circuit complexity of functions) Prove the following
facts:
1. The circuit complexity of any Boolean function is at most exponential.
Guideline: f
n
: {0, 1}
n
→{0, 1}can be computed by a circuit of size O(n2
n
)
that implements a look-up table. See also Exercise 1.17.
2. Some functions have polynomial circuit complexity. In particular, any func-
tion that has time complexity t (i.e., is computed by an algorithm of time
complexity t), has circuit complexity poly(t). Furthermore, the correspond-
ing circuit family is uniform.
Guideline: Consider a Turing machine that computes the function, and
consider its computation on a generic n-bit long input. The corresponding
computation can be emulated by a circuit that consists of t(n) layers such
that each layer represents an instantaneous configuration of the machine, and
the relation between consecutive configurations is captured by (“uniform”)
local gadgets in the circuit. For further details see the proof of Theorem 4.5,
which presents a similar emulation.
3. Almost all Boolean functions require exponential circuit complexity. Specif-
ically, show that the number of functions mapping {0, 1}
n
to {0, 1}that can be
computed by some circuit of size s is smaller than s
2s
, which is smaller than
2
2
n
unless 2s log
2
s ≥ 2
n
. Note that the total number of functions mapping
{0, 1}
n
to {0, 1} is 2
2
n
.
Guideline: Show that, without loss of generality, we may consider circuits
of bounded fan-in. The number of such circuits having v vertices is at
most
2 ·
v
2
+ v
v
, where for each gate we either have a choice of binary
operation (i.e., ∧ or ∨) and two feeding vertices or a choice of a single
feeding vertex (for a ¬-gate). Note that the input terminals each have a
choice of an index of an input variable in [n], and by our conventions v ≥ n.
Exercise 1.16 (the class P/poly) We denote by P/ the class of decision prob-
lems that can be solved in polynomial time with advice of length , and by
P/poly the union of P/p taken over all polynomials p. Prove that a decision
problem is in P/poly if and only if it has polynomial circuit complexity.
Guideline: Suppose that a problem can be solved by a polynomial-time algo-
rithm A using the polynomially bounded advice sequence (a
n
)
n∈N
. We obtain
a family of polynomial-size circuits that solves the same problem by observing
that the computation of A(a
|x|
,x) can be emulated by a circuit of poly(|x|)-
size, which incorporates a
|x|
and is given x as input. That is, we construct a
circuit C
n
such that C
n
(x) = A(a
n
,x) holds for every x ∈{0, 1}
n
(analogously