Information Technology Reference
In-Depth Information
Shannon [
307
] developed lower bounds for two-terminal switching circuits of the type
given in Section
2.12
on circuit size. Muller [
224
] extended the techniques of Shannon to
derive the lower bounds on circuit size given in Theorem
2.12.1
. Shannon and Riordan [
281
]
developed a lower bound of
Ω(
2
n
/
log
n
)
on the size of Boolean formulas, circuits in which the
fan-out of each gate is 1. As seen in Chapter
9
, such bounds readily translate into lower bounds
on depth of the form given Theorem
2.12.2
. Gaskov, using the Lupanov representation, has
derived a comparable upper bound [
110
].
The upper bound on circuit size given in Section
2.13
is due to Lupanov [
208
]. Shannon
and Riordan [
281
] show that a lower bound of
Ω(
2
n
/
log
n
)
must apply to the formula size
(see Definition
9.1.1
) of most Boolean functions on
n
variables. Given the relationship of
Theorem
9.2.2
between formula size and depth, a depth lower bound of
n
−
log log
n
−
O
(
1
)
follows.
Early work on circuits and circuit complexity is surveyed by Paterson [
237
]andcoveredin
depth by Savage [
287
]. More recent coverage of this subject is contained in the survey article
by Bopanna and Sipser [
50
] and topics by Wegener [
360
] and Dunne [
92
].
Search WWH ::
Custom Search