Information Technology Reference
In-Depth Information
Boolean functions on
n
variables require formula size
Ω(
n
log log
n
)
over the same basis. The
16 exceptional functions have linear formula size.
Using counting arguments such as those given in Section
2.12
, Gilbert [
114
]hasshown
that most monotone Boolean functions on
n
variables have a circuit size that is
Ω(
2
n
/n
3
/
2
)
.
Red'kin [
275
] has shown that the lower bound can be achieved to within a constant multi-
plicative factor by every monotone Boolean function.
Tiekenherinrich [
330
]gavea4
n
lower bound to the monotone circuit size of a simple
function. Dunne [
87
] derived a 3
.
5
n
lower bound on the monotone circuit size for the major-
ity function.
The lower bound on the monotone circuit size of binary sorting (Theorem
9.6.1
)isdue
to Lamagna and Savage [
188
] using an argument patterned after that of Van Voorhis [
351
]for
comparator-based sorting networks. Muller and Preparata [
225
,
226
] demonstrate that binary
sorting over the standard basis has circuit size
O
(
n
)
.(SeeTheorem
2.11.1
.) Pippenger and
Va l i an t [
253
]andLamagna[
187
]demonstratean
Ω(
n
log
n
)
lower bound on the monotone
circuit size of merging. These results are established in Section
9.6.1
.Thesortingnetwork
designed by Ajtai, Komlos, and Szemeredi [
14
] when specialized to Boolean data yields a
monotone circuit of size
O
(
n
log
n
)
for binary sorting.
The first proof that the monotone circuit size of
n
n
Boolean matrix multiplication
(see Section
9.6.2
)is
Ω(
n
3
)
was obtained by Pratt [
256
]. Later Paterson [238] and Mehlhorn
and Galil [
218
]demonstratedthatitisexactly
n
2
(
2
n
×
1
)
.Weiss[
361
] discovered a simple
application of the function-replacement method to both Boolean convolution and Boolean
matrix multiplication, as summarized in Corollary
9.6.1
and Theorem
9.6.5
.(Wegener[
360
,
p. 170] extended Weiss's result to include the number of
OR
s.) Wegener [
357
]hasexhibitedan
n
-input,
n
-output Boolean function (Boolean direct product) whose monotone circuit size is
Ω(
n
2
)
. Earlier several authors examined the class of multi-output functions known as
Boolean
sums
in which each output is the
OR
of a subset of inputs. Neciporuk [
231
]gaveanexplicit
set of Boolean sums and demonstrated that its monotone circuit size is
Ω(
n
3
/
2
)
.Thislower
bound for such functions was independently improved to
Ω(
n
5
/
3
)
by Mehlhorn [
216
]and
Pippenger [
250
]. More recently, Andreev [
23
] has constructed a family of Boolean sums with
monotone circuit size that is
Ω(
n
2
−
)
for every fixed
>
0.
The first super-polynomial lower bound on the monotone circuit size of the clique function
was established by Razborov [
270
]. Shortly afterward, Andreev [
22
], using similar methods,
gave an exponential lower bound on the monotone circuit size of a problem in
NP
.Becausethe
clique function is complete with respect to monotone projections [
310
,
344
], this established
an exponential lower bound for the clique function. Alon and Bopanna [
17
], by strengthen-
ing Razborov's method, gave a direct proof of this fact, giving a lower bound exponential in
−
Ω
(
n/
log
n
)
1
/
3
. The stronger lower bound given in Theorem
9.6.6
, which is exponential
in
Ω(
n
1
/
3
)
,isduetoAmanoandMaruoka[
20
]. They apply
bottleneck counting
,anideaof
Haken [
125
], to establish this result. Amano and Maruoka [
20
] have also extended the approx-
imation method to circuits that have negations only on their inputs and for which the number
of inputs carrying negations is small. They show that, even with a small number of negations,
an exponential lower bound on the circuit size of the clique function can be obtained.
Having shown that monotone circuit complexity can lead to exponential lower bounds,
Razborov [
271
] then cast doubt on the likelihood that this approach would lead to exponential
non-monotone circuit size bounds by proving that the matching problem on bipartite graphs,
a problem in
P
, has a super-polynomial monotone circuit size. Tardos [
324
]strengthened
Search WWH ::
Custom Search