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