Information Technology Reference
In-Depth Information
THEOREM
9.6.7
Let
Ω
0
be the standard basis and
f
:
B
n
→B
≤
k
≤
n
. Then there exists
0
such that
C
Ω
0
f
[
k
]
C
Ω
0
(
f
)
n
−
O
(
1
)
≤
≤
C
Ω
0
(
f
)+
O
(
n
)
Proof
The first inequality follows from Lemma
9.6.9
, the following inequality and the
observation that at least one term in an average is greater than or equal to the average.
C
Ω
0
f
[
0
]
,
f
[
1
]
,
...
,
f
[
n
]
C
Ω
0
(
f
[
i
]
)
≤
i
The second inequality uses the fact that the
k
th slice of a function can be expressed as
f
[
k
]
(
x
)=
τ
(
n
)
k
(
x
)
f
(
x
)+
τ
(
n
)
k
+
1
(
x
)
Since
τ
(
n
j
(
x
)
can be realized by a circuit of size linear in
n
(see Theorem
2.11.1
), the second
inequality follows.
In Theorem
9.6.9
we show that the monotone circuit size of slice functions provides a
lower bound on their non-monotone circuit size up to a polynomial additive term. Before
establishing this result we introduce the concept of pseudo-negation. A
pseudo-negation
for
variable
x
i
in a
m
onotone Boolean function
f
:
n
is a function
h
i
such that replacing
each instance of
x
i
in a circuit for
f
by
h
i
does not chan
g
e the value computed by the circuit.
Thus, the pseudo-negation
h
i
acts like the real negation
x
i
.
In Theorem
9.6.9
we also show that for 1
B
→B
≤
i
≤
n
the punctured threshold function
τ
(
n
)
k
,
n
, which depends on all the variables except
x
i
, is a pseudo-negation for a
k
th
slice of every monotone function. Since for a given
k
each of these threshold functions can be
realized by a monotone circuit of size
O
(
n
log
n
)
(see Theorem
6.8.2
), they can all be realized
by a monotone circuit of size
O
(
n
2
log
n
)
. Although this result can be used in Theorem
9.6.9
,
the following stronger result is used instead.
We now describe a circuit that computes all of the above pseudo-negations efficiently. This
circuit uses the
complementary number system
, a system that associates with each integer
i
in the set
(
n
)=
¬i
:
B
→B
{
0, 1, 2,
...
,
n
−
1
}
the complementary set
(
n
)
−{
i
}
.Itmakesuseof
results on sorting networks found in Chapter
6
.
THEOREM
9.6.8
The set
{τ
(
n
)
|
1
≤
i
≤
n
}
of pseudo-negations can be realized by a monotone
k
,
¬
i
circuit of size
O
(
n
log
2
n
)
.
Proof
We assume that
n
=
2
s
. If not, add variables with value 0 to increase the number to
the next power of 2. This does not change the value of the function on the first
n
variables.
For this proof let the pseudo-negations
τ
(
n
)
k
,
1andonthe
variables whose indices are in
(
n
)
. (We subtract 1 from each index.) Let
D
i
=
(
n
)
i
be defined for 0
≤
i
≤
n
−
¬
−
denote the indices of the variables on which
τ
(
n
)
k
,
{
i
}
i
depends. An efficient monotone
¬
τ
(
n
)
k
,
circuit to compute all the pseudo-negations
{
¬i
|
i
∈
(
n
)
}
isbasedonanefficient
decomposition of the sets
{
D
i
|
i
∈
(
n
)
}
.
For
a
,
b
≥
0, let
U
a
,
b
be defined by
a
2
b
+
c
2
b
U
a
,
b
=
{
|
0
≤
c
≤
−
1
}
Search WWH ::
Custom Search