Information Technology Reference
In-Depth Information
LEMMA
9.6.3
Every monotone circuit for Boolean matrix multiplication
f
(
n
,
m
,
p
)
MM
requires at least
n
(
m
1
)
p
OR
gates.
Proof
In the proof of Theorem
9.6.4
we identified a set
E
i
of gates called the bottleneck
associated with each input variable
x
i
. We demonstrated that each of these gates can be
−
eliminated by setting
x
i
=
0andthat
E
i
has at least
√
d
i
−
V
i
|
is the number of circuit outputs that depend essentially on
x
i
and have at least two prime
implicants. These results were shown by proving that all gates in
E
i
are
OR
gates and that
the
t
th of these gates' associated function contains a prime implicant of the form
x
i
t
∧
u
i
gates, where
d
i
−
u
i
=
|
y
j
t
for
x
i
t
=
x
i
. We then demonstrated that the dependence of the outputs in
V
i
on the input
x
i
can be eliminated by setting
x
i
t
=
y
j
t
=
1for1
≤
t
≤
E
i
but that this contradicts
|
E
i
|
2
<
|
V
i
|
the definition of a semi-definite bilinear form if
. Finally, we proved that by
setting
x
i
=
0eachofthegatesin
E
i
could be eliminated. For this lemma, we need only
strengthen the lower bound on
E
i
for matrix multiplication.
Consider a minimal circuit. The proof is by induction on
m
, with the base case being
m
=
1. In the base case
c
i
,
j
=
a
i
,1
∧
b
1,
j
for 1
≤
i
≤
n
and 1
≤
j
≤
p
and no
OR
s
are needed. As inductive hypothesis we assume that
f
(
n
,
m−
1,
p
)
MM
requires at least
n
(
m
−
2
)
p
OR
gates. We show that setting any column of
A
in
f
(
n
,
m
,
p
)
MM
to 0 eliminates
np
OR
gates
and reduces the problem to an instance of
f
(
n
,
m−
1,
p
)
MM
It follows that
f
(
n
,
m
,
p
)
MM
.
requires
n
(
m
1
)
p
OR
gates.
When
m
−
2, each output function
c
i
,
j
has at least two prime implicants. We apply
the bottleneck argument to this case. Consider the bottleneck
E
i
,
k
associated with input
variable
a
i
,
k
. We show that
≥
p
, from which it follows that at least
p
OR
gates can be
eliminated by setting
x
i
,
k
=
0. This reduces the problem to another set of bilinear forms.
Repeating this for 1
|
E
i
,
k
|≥
≤
i
≤
n
, we eliminate
np
OR
gates, one column of
A
, and one row of
B
.Let
V
i
,
j
=
{
c
i
,
j
|
1
≤
j
≤
p
}
be the outputs that depend on
a
i
,
k
.
To s h ow t h a t
|
E
i
,
k
|≥
p
,letthe
t
hgateof
E
i
,
k
compute
x
i
t
∧
y
j
t
for
x
i
t
=
a
i
,
k
.
Here
x
i
t
=
a
i
t
,
k
t
and
y
j
t
=
b
l
t
,
j
t
for some
i
t
,
k
t
,
l
t
,and
j
t
.
If we set all entries in
{
a
i
t
,
k
t
|
≤
t
≤|
E
i
,
k
|} ∪ {
b
l
t
,
j
t
|
≤
t
≤|
E
i
,
k
|}
1
1
to 1, we eliminate all dependence of
outputs in
V
i
,
k
on
a
i
,
k
. However, since
|
V
i
,
j
|
=
p
,theset
{
b
l
t
,
j
t
}
must contain at least one
variable used in
c
i
,
j
for each 1
≤
j
≤
p
.Thus,
|
E
i
,
k
|≥
p
.
We now derive a lower bound on the number of
AND
gates needed for Boolean matrix
multiplication.
LEMMA
9.6.4
Every monotone circuit for Boolean matrix multiplication
f
(
n
,
m
,
p
)
MM
requires at least
nmp
AND
gates.
Proof
Consider a minimal circuit. The proof is by induction on
m
, the base case being
m
=
1.Inthebasecase
c
i
,
j
=
a
i
,1
p
and
np
AND
sare
needed, since
np
results must be computed, each requiring one
AND
, and all functions are
different. As inductive hypothesis we assume that
f
(
n
,
m−
1,
p
)
MM
∧
b
1,
j
for 1
≤
i
≤
n
and 1
≤
j
≤
requires at least
n
(
m
−
1
)
p
AND
gates. We show that setting any column of
A
in
f
(
n
,
m
,
p
)
MM
to 1 and the corresponding
row of
B
to 0 eliminates
np
AND
gates and reduces the problem to an instance of
f
(
n
,
m−
1,
p
)
MM
.
It follows that
f
(
n
,
m
,
p
)
MM
requires
nmp
AND
gates.
m
let
G
i
,
j
be a gate closest to inputs computing a function
g
such that
PI
(
g
)
contains
a
i
,
k
∧
For arbitrary 1
≤
k
≤
b
k
,
j
.Sincethegateassociatedwith
c
i
,
j
has
a
i
,
k
∧
b
k
,
j
as a
Search WWH ::
Custom Search