Information Technology Reference
In-Depth Information
large as
(
2
/
(
k
+
1
))(log
2
e
)
k
j
=
1
y
log
e
ydy
, whose value is
(
2
/
(
k
+
1
))[(
k
2
/
2
)log
2
k
−
(
1
/
4
)
k
2
(log
2
e
)+
1
/
4
]
. From this the desired conclusion follows, since
k
=
n/
2.
We now present lower bounds on the monotone circuit size of Boolean convolution and
Boolean matrix multiplication, problems for which the gap between the monotone and non-
monotone circuit size is much larger than for sorting and merging.
9.6.2 The Function Replacement Method
The
function replacement method
simplifies monotone circuits by replacing a function com-
puted at an internal vertex by a new function without changing the function computed by the
overall circuit. Since a replacement step eliminates gates and reduces a problem to a subprob-
lem, the method provides a basis for establishing lower bounds on circuit complexity using
proof by induction.
We describe two replacement rules and then apply them to Boolean convolution and
Boolean matrix multiplication. These two problems are defined in the usual way except that
variables assume Boolean values in
B
and the multiplication and addition operators are inter-
preted as
AND
and
OR
, respectively.
REPLACEMENT RULES
A
replacement rule
is a rule that allows a function computed at a vertex
of a circuit to be replaced by another without changing the function computed by the circuit.
Before stating such rules for monotone functions, we introduce some terminology.
DEFINITION
9.6.1
Let
x
denote the variables of a Boolean function
f
:
B
n
.An
implicant
of
f
is a product (
AND
),
π
, of a subset of the literals of
f
(the variables and their complements)
such that if
π
(
x
)=
1
on input
n
-tuple
x
,then
f
(
x
)=
1
. (This is denoted
π
→B
≤
f
.) The
set of
implicants
of a function
f
is denoted
I
(
f
)
.
An implicant
π
of a Boolean function
f
is a
prime implicant
if there is no implicant
π
1
different from
π
such that
π
≤
π
1
≤
f
.The
set of prime implicants
of a function
f
is denoted
PI
(
f
)
.
A
monotone implicant
(also called a
monom
) of a monotone Boolean function
f
:
→B
is the product (
AND
)
π
of uncomplemented variables of
f
such that if
π
(
x
)=
1
on input
n
-tuple
x
,then
f
(
x
)=
1
.The
empty monom
has value
1
.The
set of monotone implicants
of a
function
f
is denoted
I
mon
(
f
)
.
A monotone implicant
π
of a Boolean function
f
is a
monotone prime implicant
if there is
no monotone implicant
π
1
different from
π
such that
π
B
n
≤
π
1
≤
f
.The
set of monotone prime
implicants
of a function
f
is denoted
PI
mon
(
f
)
.
The products in the sum-of-products expansion (SOPE) are (non-monotone) implicants
of a Boolean function. If a function is monotone, it has monotone implicants (monoms). The
prime implicants of a Boolean function
f
define it completely; the
OR
of its prime implicants
is a formula representing it. In the case of a monotone Boolean function, the prime implicants
are monotone prime implicants. (See Problem
9.33
.)
When it is understood from context that an implicant or prime implicant is monotone,
we may omit the word “monotone” and use the subscript “mon.” This will be the case in this
section.
Search WWH ::
Custom Search