Information Technology Reference
In-Depth Information
assume that such a circuit has negations only on input variables. By Problem
9.11
there is
such a circuit.
Given an instance defined by
u
f
−
1
(
1
)
, the players follow a path
from the circuit output to an input at which
u
and
v
differ. The invariant that applies at
each step is that Player I (which holds
u
) simulates an
AND
gate whose value on
u
is 0
whereas Player II (which holds
v
) simulates an
OR
gate whose value on
v
is 1. The bits
transmitted by one player to the other specify which input to the current gate to follow on
the way from the output vertex to an input vertex of the circuit for
f
.
The proof is by induction. The base case applies to those Boolean functions
f
for which
D
Ω
0
(
f
)=
0. In this case
f
is either
x
i
or
x
i
for some
i
where
x
i
is an input variable of
f
. Thus, for each instance of the problem, both players know in advance a variable (namely,
x
i
)onwhich
u
and
v
differ. Hence,
C
(
U
,
V
)=
0 and the base case is established.
For the induction step, either
f
=
f
1
∧
f
−
1
(
0
)
and
v
∈
∈
f
2
. Consider the first case; the
second is treated in a similar fashion. Obviously
D
Ω
0
(
f
)=max(
D
Ω
0
(
f
1
)
,
D
Ω
0
(
f
2
)) +
1.
(We are considering circuits of minimal depth.) Let
U
j
=
U
f
2
or
f
=
f
1
∨
f
−
j
(
0
)
for
j
=
1, 2. Since
(
U
j
,
V
)
is a communication game associated with
f
j
(
f
j
must have value 1 on
V
)and
D
Ω
0
(
f
j
)
<D
Ω
0
(
f
)
,byinduction
C
(
U
j
,
V
)
∩
D
Ω
0
(
f
j
)
.
Since the output gate is
AND
(the other case is treated similarly), both
f
1
and
f
2
have
value 1 on
V
, but at least one of them has value 0 on
U
. We use the following protocol for
(
U
,
V
)
:PlayerIsends0if
u
≤
∈
U
1
(associated with the input
f
1
to this
AND
gate) and 1
if
u
U
2
(associated with the input
f
2
). (If the output gate is
OR
, we observe that at least
one of
f
1
and
f
2
has value 1 on
V
and define
V
1
=
V
∈
f
−
2
(
1
)
.
Player II sends a bit to specify the set containing
v
.) After the first move the players follow
the protocol for the
f
j
defined by the bit sent by Player I. Thus, when the output gate is
AND
the following bound holds:
f
−
1
(
1
)
and
V
2
=
V
∩
∩
C
(
U
,
V
)
≤
1
+max
j
=
1,2
(
C
(
U
j
,
B
))
≤
1
+max(
D
Ω
0
(
f
1
)
,
D
Ω
0
(
f
2
)) =
D
Ω
0
(
f
)
The same bound holds when the output gate is
OR
.
WenowprovethesecondhalfofTheorem
9.7.1
.
LEMMA
9.7.2
Let
U
,
V ⊆B
n
be such that
U
∩
V
=
∅
. Then there exists a Boolean function
n
f
−
1
(
0
)
and
V
f
−
1
(
1
)
such that the following bound holds:
f
:
B
→B
with
U
⊆
⊆
C
(
U
,
V
)
Proof
In this proof we show how to define a Boolean function and a circuit for it from a
protocol for
(
U
,
V
)
. From the protocol a tree is constructed. The root is associated with the
player who sends the first bit. As in the proof of Lemma
9.7.1
, Player I is associated with
AND
gates and Player II with
OR
gates. Thus, if the protocol specifies that Player I makes
the first move, the root is labeled
AND
. The two possible descendants are labeled with the
player who makes the next transmission or by a variable or its negation (the answer) if this
is the last transmission under the protocol. The function associated with the protocol is the
function computed by the circuit so constructed.
We establish the result by induction. The base case applies to sets
U
and
V
for which
C
(
U
,
V
)=
0. In this case, there is an index
i
known in advance to both players on which
u
D
Ω
0
(
f
)
≤
∈
U
and
v
∈
V
differ. Since either
u
i
=
1or
u
i
=
0forall
u
∈
U
(
v
i
has the
Search WWH ::
Custom Search