Information Technology Reference
In-Depth Information
m
with respect to the basis
Ω
,
D
Ω
(
f
)
,is
the depth of the smallest depth circuit for
f
over the basis
Ω
.The
circuit depth with fan-out
s
,
denoted
D
s
,
Ω
(
f
)
,isthecircuitdepthof
f
when the circuit fan-out is limited to at most
s
.
The
formula size
of a Boolean function
f
:
The
circuit depth
of a binary function
f
:
B
n
→B
n
with respect to a basis
Ω
,
L
Ω
(
f
)
,isthe
minimal number of input vertices in any circuit of fan-out 1 for
f
over the basis
Ω
.
B
→B
It is important to note the distinction between formula and circuit size: in the former
the number of input vertices is counted, whereas in the latter it is the number of gates. A
relationship between the two is shown in Lemma
9.2.2
.
9.2 Relationships Among Complexity Measures
In this section we explore the effect on circuit complexity measures of a change in either the
basis or the fan-out of a circuit. We also establish relationships between circuit depth and
formula size.
9.2.1 Effect of Fan-Out on Circuit Size
It is interesting to ask how the circuit size and depth of a function change as the maximal fan-
out of a circuit is reduced. This issue is important in understanding these complexity measures
and in the use of technologies that limit the fan-out of gates. The following simple facts about
trees are useful in comparing complexity measures. (See Problem
9.2
.)
LEMMA
9.2.1
A rooted tree of maximal fan-in
r
containing
k
vertices has at most
k
(
r −
1
)+
1
leaves and a rooted tree with
l
leaves and fan-in
r
has at most
l
−
1
vertices with fan-in
2
or more
and at most
2
(
l
−
1
)
edges.
From the above result we establish the following connection between circuit size with fan-
out 1 and formula size.
LEMMA
9.2.2
Let
Ω
be a basis of fan-in
r
.Foreach
f
:
B
n
→B
the following inequalities hold
between formula size,
L
Ω
(
f
)
, and fan-out-
1
circuit size,
C
1,
Ω
(
f
)
:
2
Proof
The first inequality follows from the definition of formula size and the first result
stated in Lemma
9.2.1
in which
k
=
C
1,
Ω
(
f
)
. The second inequality also follows from
Lemma
9.2.1
. A tree with
L
Ω
(
f
)
leaves has at most
L
Ω
(
f
)
(
L
Ω
(
f
)
−
1
)
/
(
r
−
1
)
≤
C
1,
Ω
(
f
)
≤
3
L
Ω
(
f
)
−
−
1verticeswithfan-inof2or
more and at most 2
(
L
Ω
(
f
)
1
)
edges between vertices (including the leaves). Each of these
edges can carry a
NOT
gate, as can the output gate, for a total of at most 2
L
Ω
(
f
)
−
−
1
NOT
gates. Thus, a circuit of fan-out 1 has at most 3
L
Ω
(
f
)
−
2gates.
As we now show, circuit size increases by at most a constant factor when the fan-out of the
circuit is reduced to
s
for
s
2. Before developing this result we need a simple fact about a
complete basis
Ω
, namely, that at most two gates are needed to compute the
identity function
i
(
x
)=
x
, as shown in the next paragraph. If a basis contains
AND
or
OR
gates, the identity
function can be obtained by attaching both of their inputs to the same source.
We a re done i f
Ω
contains a function such that by fixing all but one variable,
i
(
x
)
is
computed.
≥
If not, then we look for a non-monotone function in
Ω
. Since some binary
Search WWH ::
Custom Search