Information Technology Reference
In-Depth Information
where
K
(
f
)
is the lower bound given in Theorem
9.4.2
. Show that
K
(
f
)
≤
D
(
f
)
≤
λ
(
P
)
K
(
f
)
≤
D
(
f
)
≤
λ
(
P
)
Hint:
Use the fact that the largest eigenvalue of a matrix
P
satisfies
x
T
P
x
x
T
x
λ
(
P
)=max
x
=
0
Also, let
s
i
be the sum of the elements in the
i
th column of the matrix
Q
. Show that
i
s
i
=
r
,
s
p
r
,
s
.
LOWER-BOUND METHODS FOR MONOTONE CIRCUITS
9.32 Consider a monotone circuit on
n
inputs that computes a monotone Boolean function
f
:
n
. Let the circuit have
k
two-input
AND
gates, one of them the output gate,
and let these gates compute the Boolean functions
g
1
,
g
2
,
...
,
g
k
=
f
,wherethe
AND
gates are inverse-ordered by their distance from the output gate computing
f
.Sincethe
function
g
j
is computed using the values of
x
1
,
x
2
,
...
,
x
n
,
g
1
,
...
,
g
j−
1
, show that
g
j
can be computed using at most
n
+
j
B
→B
−
2two-input
OR
gates and one
AND
gate. Show
that this implies the following upper bound on the monotone circuit size of
f
:
kn
+
k
−
1
C
Ω
mon
(
f
)
≤
−
1
2
Let
C
∧
(
f
)
denote the minimum number of
AND
gates used to realize
f
over the mono-
tone basis. This result implies the following relationship:
C
Ω
mon
(
f
)=
O
(
C
∧
(
f
))
2
How does this result change if the gate associated with
f
is an
OR
gate?
9.33 Show that the prime implicants of a monotone function are monotone prime impli-
cants.
9.34 Find the monotone implicants of the Boolean threshold function
τ
(
n
)
n
:
B
→B
,
t
n
.
9.35 Using the gate-elimination method, show that
C
Ω
mon
(
τ
(
n
)
≤
t
≤
1
)
≥
2
n
−
3.
9.36 Show that an expansion of the form of equation (
9.1
)onpage
420
holds for every
monotone function.
9.37 Show that the
f
(
n
)
2
n
(
n
−
1
)
/
2
clique
,
k
:
B
→B
can be realized by a monotone circuit of size
O
(
n
n
)
.
9.38 Show that the largest value assumed by
min(
√
k
−
1
/
2,
n/
(
2
k
))
under variation of
k
is
Ω(
n
1
/
3
)
.
Search WWH ::
Custom Search