Information Technology Reference
In-Depth Information
V
i
on
x
i
. However, since inputs
have only been assigned value 1 (and not 0), this dependence on
x
i
can be eliminated only
if all functions in
V
i
have value 1; that is, at least one prime implicant of each of them is
set to 1 by this assignment. Since each variable appears in at most one prime implicant of
a function, the number of different variables
x
i
t
≤
t
≤|
E
i
|
. This eliminates all dependence of
f
r
∈
for 1
(and
y
i
t
)thataresetto1isatmost
|
E
i
|
.
|
E
i
|
2
prime implicants can be assigned value 1 by this assignment. Thus, if
Thus, at most
|
E
i
|
2
<
(
d
i
−
u
i
)
, we have a contradiction since
|
V
i
|
=(
d
i
−
u
i
)
.
OR
gates can be eliminated by setting
x
i
=
0. Since each gate is
a closest gate to an input labeled
x
i
with the stated property, there is an
OR
gate on the path
to it with
x
i
as an input. Thus, setting
x
i
=
0 eliminates one of the two inputs to the
OR
gate and the need for the gate itself.
|
E
i
|
We now show that
Since for each of the
n
input variables in
a
there are
n
output functions in
c
=
a
⊗
b
that
depend on it (
d
i
=
n
for 1
≤
i
≤
n
), the following corollary is immediate.
COROLLARY
9.6.1
Let
f
(
n
)
2
n
2
n−
1
be the Boolean convolution function. Then the
conv
:
B
→B
monotone circuit size of
f
(
n
)
conv
satisfies the following lower bound:
f
(
n
)
conv
n
3
/
2
C
Ω
mon
≥
Unfortunately, no upper bound on the monotone circuit size of
f
(
n
)
conv
is known that
matches this lower bound. A stronger statement can be made for Boolean matrix multipli-
cation.
BOOLEAN MATRIX MULTIPLICATION
Matrix multiplication over rings is discussed at length in
Section
6.3
. In this section we introduce the Boolean version. An
I
×
J
matrix
A
=[
a
i
,
j
]
,
J
, is a two-dimensional array of elements in which
a
i
,
j
is the element
in the
i
th row and
j
th column. We take the entries in a matrix to be Boolean variables.
≤
i
≤
I
and 1
≤
j
≤
1
DEFINITION
9.6.5
Let
A
=[
a
i
,
k
]
,
1
≤ i ≤ n
and
1
≤ k ≤ m
,
B
=[
b
k
,
j
]
,
1
≤ k ≤ m
and
1
≤
j
≤
p
,and
C
=[
c
i
,
j
]
,
1
≤
i
≤
n
and
1
≤
j
≤
p
,be
n
×
m
,
m
×
p
,and
n
×
p
matrices,
B
of
A
and
B
is the function
f
(
n
,
m
,
p
)
MM
np
whose value on the matrices
A
and
B
is the matrix
C
whose entry in row
i
and column
j
,
c
i
,
j
,is
defined as
nm
+
mp
respectively. The
product
C
=
A
×
:
B
→B
m
c
i
,
j
=
a
i
,
k
∧
b
k
,
j
k
=
1
In a more general context the
AND
operator
∧
and the
OR
operator
∨
are replaced by the
multiplication and addition operators over rings.
The above definition can be used as an algorithm to compute
c
i
,
j
,1
≤
i
≤
n
and 1
≤
j
p
,fromtheentriesinmatrices
A
and
B
. We call this the
standard matrix-multiplication
algorithm
.Ituses
nmp
AND
sand
n
(
m
≤
1
)
p
OR
s. We now show that every monotone circuit
for matrix multiplication requires at least this many
AND
sand
OR
s.
Clearly the matrix multiplication function is a bilinear form. We associate the entries in
A
with the tuple
x
and those in
B
with
y
. We strengthen Theorem
9.6.4
to obtain a lower
bound on the number of
OR
s needed to realize it in a monotone circuit.
−
Search WWH ::
Custom Search