Information Technology Reference
In-Depth Information
y
= ((((
x
7
∨
x
6
)
∧
(
x
5
∨
x
4
))
∨
x
3
)
∧
(
x
2
∧
x
1
))
x
3
x
2
x
1
x
7
x
6
x
5
x
4
Figure 9.1
A circuit of fan-out 1 over a basis with fan-in 2 and a corresponding formula. The
value
y
at the root is the
AND
of the value
(((
x
7
∨ x
6
)
∧
(
x
5
∨ x
4
))
∨ x
3
)
of the left subtree with
the value
(
x
2
∧ x
1
)
of the right subtree.
is complete for the monotone functions
, that is, every monotone function can be computed
by a circuit over the basis
Ω
mon
. (See Problem
2
.)
In Section
9.6
we show that some monotone functions on
n
variables require monotone
circuitswhosesizeisexponentialin
n
. In particular, some monotone functions requiring
exponential-size monotone circuits can be realized by polynomial-size circuits over the standard
basis
Ω
0
. Thus, the absence of negation can result in a large increase in circuit size.
The
bounded-depth circuit
is a circuit over the standard basis
Ω
0
where the fan-in of
AND
and
OR
gates is allowed to be unbounded, but the circuit depth is bounded. The conjunctive
and disjunctive normal forms and the product-of-sums and sum-of-products normal forms
realize arbitrary Boolean functions by circuits of depth 2 over
Ω
0
.(SeeSection
2.3
.) In these
normal forms negations are used only on the input variables. Note that any circuit over the
standard basis can be converted to a circuit in which the
NOT
gates are applied only to the
input variables. (See Problem
9.11
.)
9.1.2 Complexity Measures
We now define the measures of complexity studied in this chapter. The
depth of a circuit
is
the number of gates of fan-in 2 or more on the longest path in the circuit. (Note that
NOT
gates do not affect the depth measure.)
DEFINITION
9.1.1
The
circuit size
of a binary function
f
:
B
m
with respect to the basis
Ω
, denoted
C
Ω
(
f
)
,isthesmallestnumberofgatesinanycircuitfor
f
over the basis
Ω
.The
circuit
size with fan-out
s
, denoted
C
s
,
Ω
(
f
)
,isthecircuitsizeof
f
when the circuit fan-out is limited
to at most
s
.
n
→B
Search WWH ::
Custom Search