Information Technology Reference
In-Depth Information
is, the set of all subsets of
[
n
]
.A
monotone minterm
(
monotone maxterm
) is a minimal
set of indices of variables that if set to 1 (0) cause
f
to assume value 1 (0). (The variables
of a monotone minterm are variables in a monotone prime implicant of
f
.) Let
min
(
f
)
and
max
(
f
)
be the set of monotone minterms and monotone maxterms of
f
, respectively.
Observe that
min
(
f
)
because if they have no elements in common,
f
can
be made to assume values 0 and 1 simultaneously for some assignment to the variables of
f
,a
contradiction.
∩
max
(
f
)
=
∅
DEFINITION
9.7.2
A
monotone communication game
(
A
,
B
)
is defined by sets
A
,
B ⊆
2
[
n
]
.
An instance of the game is a pair
(
a
,
b
)
where
a
B
.
a
is assigned to Player I
and
b
is assigned to Player II. Players alternate sending messages as in the communication game,
using a predetermined protocol. The
goal
of the problem is to find an integer
i
∈
A
and
b
∈
b
.The
communication complexity
,
C
mon
(
A
,
B
)
, is defined as the minimum over all protocols
Π
of
the maximum number of bits exchanged under
Π
on any instance of
(
A
,
B
)
:
∈
a
∩
C
mon
(
A
,
B
)=mi
Π
a∈A
,
b∈B
Π(
a
,
b
)
max
We now establish a relationship between this complexity measure and the circuit depth of
a Boolean function.
THEOREM
9.7.2
For every monotone Boolean function
f
:
B
n
→B
,
D
Ω
mon
(
f
)=
C
(
f
−
1
(
0
)
,
f
−
1
(
1
)) =
C
mon
(
min
(
f
)
,
max
(
f
))
Proof
We show tha t
D
Ω
mon
(
f
)=
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
by specializing Lemmas
9.7.1
and
9.7.2
to monotone functions. In the base case of Lemma
9.7.1
since the circuit is monotone
we always discover a coordinate such that
u
i
=
0and
v
i
=
1 and negations are not needed.
Thus,
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
D
Ω
mon
(
f
)
. In Lemma
9.7.2
, since the protocol provides
a coordinate
i
such that
u
i
=
0and
v
i
=
1, the circuit defined by it is monotone and
D
Ω
mon
(
f
)
≤
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
.
We show tha t
C
(
f
−
1
(
0
)
,
f
−
1
(
1
)) =
C
mon
(
min
(
f
)
,
max
(
f
))
in two stages. First we
show that
C
mon
(
min
(
f
)
,
max
(
f
))
≤
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
. This follows because, given
≤
any
a
∈
min
(
f
)
and
b
∈
max
(
f
)
,weextend
a
and
b
to binary
n
-tuples
u
and
v
for
which
u
r
=
0for
r
b
and use the protocol for the monotone
communication game to find an index
i
such that
u
i
=
0and
v
i
=
1, that is, for which
i
∈
a
and
v
s
=
1for
s
∈
b
. Thus, the monotone communication game exchanges no more bits than the
standard game.
To s h ow t h a t
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
∈
a
∩
C
mon
(
min
(
f
)
,
max
(
f
))
, consider an instance
(
u
,
v
)
of
(
U
,
V
)
where
U
=
f
−
1
(
0
)
and
V
=
f
−
1
(
1
)
. To solve the communication
problem
(
U
,
V
)
,let
a
(
u
)
≤
∈
[
n
]
be defined by
r
∈
a
(
u
)
if and only if
a
r
=
0andlet
b
(
v
)
b
(
v
)
if and only if
v
s
=
1. The goal of the standard
communication game is to find an index
i
such that
u
i
∈
[
n
]
be defined by
s
∈
=
v
i
. It follows from the definition
of minterms and maxterms that there exist
p
∈
min
(
f
)
and
q
∈
max
(
f
)
such that
p
⊆
a
and
q
b
. Since each player has unlimited computing resources available, computation of
p
and
q
can be done with no communication cost. Now invoke the protocol on the instance
(
p
,
q
)
of the monotone communication game
(
min
(
f
)
,
max
(
f
))
.Thisprotocolreturnsan
index
i
⊆
q
that is also an index on which
u
and
v
differ. But this is a solution to
the instance of
(
u
,
v
)
of
(
f
−
1
(
0
)
,
f
−
1
(
1
))
. Thus, no more bits are communicated to solve
∈
p
∩
Search WWH ::
Custom Search